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

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

Junhao Wang

Hi, I was a master student at USC studying Computer Science.