#92
Reverse Linked List II
Medium Reverse a sublist in place
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Reverse only the nodes from position left to position right (1-indexed) in one pass.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: reverse only positions left..right.
Why this works: stand before the segment, then repeatedly move the node after the segment's first node to the front of the segment.
Example: 1→2→3→4→5, left 2, right 4
move 3 to front: 1→3→2→4→5move 4 to front: 1→4→3→2→5
✦Hints open one at a time
Walk to the node just before position left (use a dummy for left = 1).
Then repeatedly take the node after the current one and move it to the front of the sublist.
↗Approach
pre = node before the sublist; cur = first node of it. Repeat (right − left) times: move cur.next to right after pre. This "head insertion" reverses the segment in place.
</>Solution (Java)
/**
* class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } // provided by LeetCode
*/
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
for (int i = 1; i < left; i++) pre = pre.next;
ListNode cur = pre.next;
for (int i = 0; i < right - left; i++) {
ListNode move = cur.next; // node to bring to the front
cur.next = move.next;
move.next = pre.next;
pre.next = move;
}
return dummy.next;
}
}!Common mistake
Losing the connection to the part after right by not linking cur.next correctly during each move.
Complexity
- Time: O(n).
- Space: O(1).
Topic: Linked List
🎬 Episodes 40–45: video coming soon