Leetcode

Reverse Linked List II

Approach 1: Recursive

  • Time:O(n)
  • Space:O(n)

C++

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;
  }
};

JAVA

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;
  }
}

Python

class Solution:
  def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
    if left == 1:
      return self.reverseN(head, right)

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

  def reverseN(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
    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)

C++

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;  // will 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;
  }
};

JAVA

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; // will 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;
  }
}

Python

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  # will 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