Reverse Nodes in k-Group
Hard Group reversal with reconnection
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Reverse the nodes of a linked list k at a time. A final group with fewer than k nodes stays as is. Only O(1) extra memory.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: reverse every block of k nodes; leave a short last block alone.
Why this works: check k nodes exist, reverse that block, reconnect it to the previous block, move on.
Example: 1→2→3→4→5, k = 2
[2,1] [4,3] [5]2→1→4→3→5
✦Hints open one at a time
↗Approach
groupPrev starts at a dummy. Find the k-th node from groupPrev; if missing, stop. Reverse the nodes between, pointing the first node to the node after the group. Then link groupPrev to the new head and move groupPrev to the old first node (now the group's tail).
</>Solution (Java)
/**
* class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } // provided by LeetCode
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode groupPrev = dummy;
while (true) {
ListNode kth = groupPrev;
for (int i = 0; i < k && kth != null; i++) kth = kth.next;
if (kth == null) break; // fewer than k left
ListNode groupNext = kth.next;
ListNode prev = groupNext, cur = groupPrev.next;
while (cur != groupNext) { // reverse this group
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
ListNode oldFirst = groupPrev.next;
groupPrev.next = kth; // kth is the new group head
groupPrev = oldFirst; // old first is now the tail
}
return dummy.next;
}
}!Common mistake
Reversing the last short group too.
- Time: O(n).
- Space: O(1).