Reverse a Sublist of a Linked List
Solve this Problemleft and right (with left ≤ right), reverse only the nodes from position left to position right, then return the head of the modified list. Nodes outside that window keep their original order.
The single-pass solution leans on a trailing prev pointerTrailing Prev PointerKeep a pointer one step behind the section being modified. Because reversing a run of nodes only ever changes .next pointers — never values — anchoring prev right before the window means every node pulled out of the window can be re-inserted immediately after prev with a fixed, three-line relink, with no lookahead and no extra memory.: once prev is parked right before the window, the window's own first node (curr) never moves — it's exactly where it needs to end up as the window's last node — and each subsequent node just gets unhooked and re-inserted right after prev, one at a time, until the whole window is reversed.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ number of nodes in head ≤ 500 - ◆
-500 ≤ node value ≤ 500 - ◆
1 ≤ left ≤ right ≤ number of nodes in head
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
| 1 | class Solution { |
| 2 | public Node reverseSublist(Node head, int left, int right) { |
| 3 | Node dummy = new Node(0); |
| 4 | dummy.next = head; |
| 5 | Node prev = dummy; |
| 6 | for (int i = 0; i < left - 1; i++) { |
| 7 | prev = prev.next; |
| 8 | } |
| 9 | Node curr = prev.next; |
| 10 | for (int i = 0; i < right - left; i++) { |
| 11 | Node nextNode = curr.next; |
| 12 | curr.next = nextNode.next; |
| 13 | nextNode.next = prev.next; |
| 14 | prev.next = nextNode; |
| 15 | } |
| 16 | return dummy.next; |
| 17 | } |
| 18 | } |
| 19 |
dummyA dummy node lets prev walk right up to the node before position left, even when left is 1. prev starts at dummy.
Approach & Solutions
Brute Force — Collect Values, Reverse the Sub-Range, Write Back
GoodCopy every node's value into an array, reverse just the [left, right] slice of that array with a two-pointer swap, then walk the list once more writing the (possibly-swapped) values back into the same nodes in order. Correct, and it never touches a single .next pointer — but it costs an extra array the size of the whole list, and two full passes plus the swap pass, where the optimal solution needs one pass and no extra memory.
O(n)O(n)1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public Node reverseSublist(Node head, int left, int right) {
9 List<Integer> vals = new ArrayList<>();
10 Node curr = head;
11 while (curr != null) {
12 vals.add(curr.val);
13 curr = curr.next;
14 }
15 int lo = left - 1, hi = right - 1;
16 while (lo < hi) {
17 int temp = vals.get(lo);
18 vals.set(lo, vals.get(hi));
19 vals.set(hi, temp);
20 lo++;
21 hi--;
22 }
23 curr = head;
24 for (int v : vals) {
25 curr.val = v;
26 curr = curr.next;
27 }
28 return head;
29 }
30}Optimal — Reverse In Place With a Trailing Prev
OptimalWalk prev to the node right before position left. The node right after prev — call it curr — is the window's first node, and it will end up as the window's LAST node once reversed, so it never has to move. Then, (right - left) times: pull the node right after curr out of the list, and re-insert it immediately after prev. Each pulled node lands one step earlier in the window than the last, building the reversed order one relink at a time — with no new nodes and no extra memory.
O(n)O(1)1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public Node reverseSublist(Node head, int left, int right) {
9 Node dummy = new Node(0);
10 dummy.next = head;
11 Node prev = dummy;
12 for (int i = 0; i < left - 1; i++) {
13 prev = prev.next;
14 }
15 Node curr = prev.next;
16 for (int i = 0; i < right - left; i++) {
17 Node nextNode = curr.next;
18 curr.next = nextNode.next;
19 nextNode.next = prev.next;
20 prev.next = nextNode;
21 }
22 return dummy.next;
23 }
24}