Reverse in groups of k
Reverse every full run of k nodes in turn, leaving a short last run alone, by repeating the pull-to-front routine group after group. About 18 minutes.
Check first, then reverse
You can now reverse a section. To reverse every run of k nodes, stand before the first run and look ahead: are there k nodes? If so, reverse them by pulling each of the k minus 1 nodes behind the first to the front of the run.
If fewer than k nodes remain, the run is too short, so it must be left exactly as it is. That check comes before any changes.
node, cnt = prev.next, 0
while node:
node = node.next
cnt += 1
enough = cnt >= kThree nodes remain in the first run: 4, 8, 1. Reverse them: 1, 8, 4.
The next standing place
After reversing a run, the old first node cur is now at the back of the run, and the next run starts right after it. So cur is the node to stand on for the next run.
Repeat until the look-ahead finds fewer than k nodes. With k equal to 1 nothing changes, and the loop still ends because the standing node advances every round.
prev = cur
With k equal to 3 and a list of 7 nodes, how many nodes are in a run that is left unreversed?
- A1, the last node
- B0
- C3
Show the answer
1, the last node. Two full runs of 3 are reversed, leaving 1 node that does not fill a run.
Reverse nodes in k-groups
Given the head of a linked list and an integer k, reverse the nodes of the list k at a time and return the new head. If the number of nodes is not a multiple of k, the nodes left over at the end stay in their original order. Relink the existing nodes; do not change the values.
head = [1, 2, 3, 4, 5], k = 2 → [2, 1, 4, 3, 5]
0 ≤ number of nodes ≤ 5,000 · 1 ≤ k ≤ 5,000