Core Insight Before changing a link, save the only pointer that would otherwise be lost.
Common Pitfall Always store next before redirecting current.next.
Description
Reverse nodes in k-group of a linked list.
Constraints
- Time Complexity:
O(n) - Space Complexity:
O(1)
Tags
linked-listrecursion
Implementation Plan Translate the invariant into these small, testable moves.
- Initialize the pointers.
- Save the next node.
- Rewire the current node.
- Advance both pointers until the list is consumed.
def reverseKGroup(head, k):
dummy = ListNode(0, head)
groupPrev = dummy
while True:
kth = getKth(groupPrev, k)
if not kth:
break
groupNext = kth.next
prev, curr = kth.next, groupPrev.next
while curr != groupNext:
tmp = curr.next
curr.next = prev
prev = curr
curr = tmp
tmp = groupPrev.next
groupPrev.next = kth
groupPrev = tmp
return dummy.next
def getKth(curr, k):
while curr and k > 0:
curr = curr.next
k -= 1
return curr