LeetCode Entry

92. Reverse Linked List II

7.09.2023 medium 2023 kotlin

Reverse a part of Linked List

92. Reverse Linked List II medium blog post substack

image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/332

Problem TLDR

Reverse a part of Linked List

Intuition

We need to find a point where to start reversing after left steps, then do the reversing right - left steps and finally connect to tail.

Approach

  • use Dummy head technique to avoid reversed head corner case
  • better do debug right in the code

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code

    fun reverseBetween(head: ListNode?, left: Int, right: Int): ListNode? {
      val dummy = ListNode(0).apply { next = head }
      var prev: ListNode? = dummy
      var curr = prev             // d-1-2-3-4-5  2 4
      repeat(left) {              // pc
        prev = curr               // p c
        curr = curr?.next         //   p c
      }
      val head = prev             // d-1-2-3-4-5  2 4
      val tail = curr             //   h t
      prev = curr
      curr = curr?.next           //     p c
      repeat(right - left) {      //     p c n
        val next = curr?.next     //      <p c n
        curr?.next = prev         //     p<c n
        prev = curr               //      <p<c n
        curr = next               //     2<p c
      }                           //     2<3<p c
      head?.next = prev           // d-1-2-3-4-5  2 4
      tail?.next = curr           //   h t<3<p c
      return dummy.next
    }