92. Reverse Linked List II

Reference: LeetCode EPI 7.2
Difficulty: Medium

My Post: 0 ms Java Solution (Iteration & Recursion) Idx is important!

Problem

Reverse a linked list from position $m$ to $n$. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

1 2	Input: 1->2->3->4->5->NULL, m = 2, n = 4 Output: 1->4->3->2->5->NULL

Analysis

Focus on One-Pass Iteration!

One-Pass Iteration

The drawback of the above approach is that it requires two passes over the sublist.
Once we reach the m-th node, we start the reversing process and keep counting.
Once we reach the n-th node, we stop the reversion process and link the reversed section with the unreversed sections.

//       2         4

//  1    2    3    4    5
//  bef oldH  p    nT

//  1    3    2    4    5
//  bef      oldH  p    nT

//  1    4    3    2    5
//  bef           oldH  p

public ListNode reverseBetween(ListNode head, int m, int n) {
  if (head == null || head.next == null || m > n) {
    return head;
  }
  // assume m and n are valid
  ListNode dummy = new ListNode(-1);
  dummy.next = head;
  ListNode before = dummy;
  int count = m; // m = 2
  while (count > 1) {
    before = before.next;
    --count;
  }
  
  ListNode oldHead = before.next;
  ListNode p = oldHead.next;
  while (m < n) {
    ListNode nextTemp = p.next;
    p.next = before.next;
    before.next = p;
    oldHead.next = nextTemp;
    // update
    p = nextTemp;
    ++m;
  }
  return dummy.next;
}

Time: $O(N)$
Space: $O(1)$

Two-Pass Iteration

We can treat this problem as a pure list reversal problem, but we need to locate the m-th node and n-th node.

Get the list between $m$ and $n$.
Reverse the list.
Concatenate the list with the list before $m$ and the list after $n$.

Note:

Using a count variable brings about clean code.
Use a dummy node to get rid of null check.
Use two pointers p and prev. After reversal, we need to update the next pointer of (m-1)-th node.

// Iteration
public ListNode iterationSolution(ListNode head, int m, int n) {
  if (m == n) return head;
  ListNode dummy = new ListNode(-1);
  dummy.next = head;
  ListNode p = head;
  ListNode prev = dummy;
  int count = 1;
  while (count < m) { // before m
    prev = p;
    p = p.next;
    ++count;
  } // now: p -> m-th node
  ListNode mthNode = p;
  while (count < n) { // between m and n
    p = p.next;
    ++count;
  } // now: p -> n-th node
  ListNode rest = p.next; // the nodes after n-th node
  p.next = null;
  ListNode tailNode = mthNode;
  mthNode = reverse(mthNode);
  prev.next = mthNode;
  tailNode.next = rest; // connect the rest of the nodes
  return dummy.next;
}

Reverse helper:

// pure reverse
private ListNode reverse(ListNode x) {
  if (x == null || x.next == null) {
    return x;
  }
  ListNode ret = reverse(x.next);
  x.next.next = x;
  x.next = null;
  return ret;
}

Time: $O(N)$
Space: $O(1)$

Recursion

Write a recursive function that does not really reverse the list, but locate the nodes $m$ and $n$.

Use a pure reverse function to reverse the list.

Here is the helper function.

private ListNode reverseAmong(ListNode x, int m, int n, int count) {
  if (count >= n) { // points to the n-th node
    return x;
  }
  if (count < m) { // not within range
    x.next = reverseAmong(x.next, m, n, count + 1);
    return x;
  }
  if (count == m) { // points to the m-th node
    ListNode nthNode = reverseAmong(x.next, m, n, count + 1);
    ListNode rest = nthNode.next; // nodes that after n-th
    nthNode.next = null; // make the list m~n. Set null for reverse
    ListNode tailNode = x;
    x = reverse(x); // reverse the m~n nodes
    tailNode.next = rest; // rest = null / nodes that are after n-th
    return x;
  }
  // points to the nodes between (m, n)
  return reverseAmong(x.next, m, n, count + 1);
}

Time: $O(N)$
Space: $O(N)$ in the worst case when we have to reverse the entire list.

Comment