Skip to content

92. Reverse Linked List II 👍

Approach 1: Recursive

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  ListNode* reverseBetween(ListNode* head, int left, int right) {
    if (left == 1)
      return reverseN(head, right);

    head->next = reverseBetween(head->next, left - 1, right - 1);

    return head;
  }

 private:
  ListNode* reverseN(ListNode* head, int n) {
    if (n == 1)
      return head;

    ListNode* newHead = reverseN(head->next, n - 1);
    ListNode* headNext = head->next;
    head->next = headNext->next;
    headNext->next = head;

    return newHead;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  public ListNode reverseBetween(ListNode head, int left, int right) {
    if (left == 1)
      return reverseN(head, right);

    head.next = reverseBetween(head.next, left - 1, right - 1);

    return head;
  }

  private ListNode reverseN(ListNode head, int n) {
    if (n == 1)
      return head;

    ListNode newHead = reverseN(head.next, n - 1);
    ListNode headNext = head.next;
    head.next = headNext.next;
    headNext.next = head;

    return newHead;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
  def reverseBetween(
      self,
      head: ListNode | None,
      left: int,
      right: int,
  ) -> ListNode | None:
    if left == 1:
      return self.reverseN(head, right)

    head.next = self.reverseBetween(head.next, left - 1, right - 1)
    return head

  def reverseN(self, head: ListNode | None, n: int) -> ListNode | None:
    if n == 1:
      return head

    newHead = self.reverseN(head.next, n - 1)
    headNext = head.next
    head.next = headNext.next
    headNext.next = head
    return newHead

Approach 2: Iterative

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  ListNode* reverseBetween(ListNode* head, int m, int n) {
    if (!head || m == n)
      return head;

    ListNode dummy(0, head);
    ListNode* prev = &dummy;

    for (int i = 0; i < m - 1; ++i)
      prev = prev->next;  // Point to the node before the sublist [m, n].

    ListNode* tail = prev->next;  // Be the tail of the sublist [m, n]

    // Reverse the sublist [m, n] one by one.
    for (int i = 0; i < n - m; ++i) {
      ListNode* cache = tail->next;
      tail->next = cache->next;
      cache->next = prev->next;
      prev->next = cache;
    }

    return dummy.next;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
  public ListNode reverseBetween(ListNode head, int m, int n) {
    if (head == null || m == n)
      return head;

    ListNode dummy = new ListNode(0, head);
    ListNode prev = dummy;

    for (int i = 0; i < m - 1; ++i)
      prev = prev.next; // Point to the node before the sublist [m, n].

    ListNode tail = prev.next; // Be the tail of the sublist [m, n].

    // Reverse the sublist [m, n] one by one.
    for (int i = 0; i < n - m; ++i) {
      ListNode cache = tail.next;
      tail.next = cache.next;
      cache.next = prev.next;
      prev.next = cache;
    }

    return dummy.next;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
  def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
    if not head and m == n:
      return head

    dummy = ListNode(0, head)
    prev = dummy

    for _ in range(m - 1):
      prev = prev.next  # Point to the node before the sublist [m, n].

    tail = prev.next  # Be the tail of the sublist [m, n].

    # Reverse the sublist [m, n] one by one.
    for _ in range(n - m):
      cache = tail.next
      tail.next = cache.next
      cache.next = prev.next
      prev.next = cache

    return dummy.next