The problem
Given the head of a linked list and a number k, reverse the nodes k at a time and return the new head. If the number of nodes left at the end is less than k, they stay as they are.
Only the arrows may change, not the values.
Examples
- Input
head = [1, 2, 3, 4, 5], k = 2
- Output
[2, 1, 4, 3, 5]
- Input
head = [1, 2, 3, 4, 5], k = 3
- Output
[3, 2, 1, 4, 5]
Constraints
- 1 ≤ k ≤ number of nodes ≤ 5000
- 0 ≤ Node.val ≤ 1000
The idea
Handle one group at a time. before is the node just ahead of the group (a dummy node at first). Walk k nodes from it to find the group’s last node, end; if the list runs out first, stop — the rest stays.
Reverse the group as in Reverse Linked List, but start prev at the node after the group rather than at nothing, so the reversed group’s tail is already attached to the rest. Then point before at end, the group’s new first node, and move before to the old first node, now last.
- Time
- O(n) — each node is counted and turned a constant number of times
- Space
- O(1)
Solution · every language run against every case
class Solution: def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]: dummy = ListNode(0, head) before = dummy # the node just before the group being reversed while True: end = before # find the group's last node, if the group is complete for _ in range(k): end = end.next if not end: return dummy.next # fewer than k left: leave them as they are after = end.next # Reverse the group, pointing its first node at what comes after it. prev, cur = after, before.next while cur is not after: cur.next, prev, cur = prev, cur, cur.next first = before.next # now the group's last node before.next = end # the old last node leads the group before = first