Description
Reverse every complete group of k linked-list nodes by changing links. Keep a shorter final group intact. Assume 1 <= k <= the list length.
Solution
def reverse_k_group(head, k):
dummy = ListNode(0, head)
before = dummy
while True:
last = before
for _ in range(k):
last = last.next
if last is None:
return dummy.next
after = last.next
previous, current = after, before.next
while current is not after:
following = current.next
current.next = previous
previous, current = current, following
old_first = before.next
before.next = last
before = old_firstExamples
Example 1
- Input
[[1,2,3,4,5],2]- Output
[2,1,4,3,5]
Reverse two pairs and keep the last node.
Example 2
- Input
[[1,2,3,4,5],3]- Output
[3,2,1,4,5]
The last two nodes form an incomplete group.
Example 3
- Input
[[1],1]- Output
[1]
A group of one is unchanged.
Approach
Find the kth node after the previous group. If absent, stop. Reverse the group's links toward the following node, reconnect its beginning, and advance to its old first node.
Time & space
O(n) time and O(1) auxiliary space, where n is the node count.