Given the head of a linked list and a positive integer k, reverse the nodes in groups of k and return the new head. If the number of nodes left at the end is less than k, keep that last part in its original order. Change the links between nodes; do not just swap values.
- 1 <= k <= n <= 5000
- 0 <= Node.val <= 1000
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
A simple approach copies values into an array, reverses each block of k and writes them back, but that uses O(n) space and only swaps values, which the problem forbids. The real solution is a careful sequence of normal list reversals. A dummy node before the head gives every group a "previous" node. For each group we first look ahead k nodes to see if a full group exists, reverse exactly those k links, and then stitch the reversed block back between its neighbours. The old first node of the group becomes its last node and the groupPrev for the next round.
Algorithm
- Create a dummy node pointing to
headand setgroupPrev = dummy. - Find
kth, the nodeksteps aftergroupPrev. If it does not exist, stop. - Remember
groupNext = kth.nextand reverse the nodes fromgroupPrev.nexttokth, pointing the first one atgroupNext. - Link
groupPrev.next = kth, and movegroupPrevto the old first node of the group. - Repeat, then return
dummy.next.
O(n)Space: O(1)class Solution: def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]: dummy = ListNode(0, head) group_prev = dummy while True: # Find the kth node of this group. kth = group_prev for _ in range(k): kth = kth.next if kth is None: return dummy.next # fewer than k nodes left group_next = kth.next # Reverse the group; its first node will point to group_next. prev, cur = group_next, group_prev.next while cur is not group_next: nxt = cur.next cur.next = prev prev = cur cur = nxt old_first = group_prev.next group_prev.next = kth # kth is the new first node group_prev = old_first # old first is now the last node