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.
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
26
27
28
29
30
31
32
33
34
35
36
37
38
//       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.
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
26
// 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:

1
2
3
4
5
6
7
8
9
10
// 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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