Linked List

1. Reverse Nodes in k-Group

Hard

Time Complexity: \(O(N)\)

Space Complexity: \(O(1)\)

Problem Statement

Given the head of a linked list, reverse the nodes of the list k at a time and return the modified list. k is a positive integer that is at most the length of the list. If the number of nodes is not a multiple of k, the left-out nodes at the end stay in their original order. Only the nodes' links may be changed, not their values.

Explanation

Use a dummy node in front of the list so the first group can be handled like every other group, and keep a pointer group_prev to the node just before the current group. For each group:

1. Find the group. Walk k steps from group_prev with getKth to get kth, the last node of the group. If it returns None, fewer than k nodes are left, so stop. Otherwise group_next = kth.next is the first node of the next group.

2. Reverse the group. Reverse the links as in a normal linked-list reversal, but start prev at group_next instead of None. The old first node then points to the next group automatically.

3. Reconnect. The old first node is now the tail of the reversed group. Save it in tmp, point group_prev.next at kth (the new head of the group), then move group_prev to tmp and repeat.

Every node is visited a constant number of times (once to find the group, once to reverse it), so the total time is \(O(N)\) with only a few pointers of extra space.

Visual Walkthrough (k = 2)

Input: 1 → 2 → 3 → 4 → 5 Output: 2 → 1 → 4 → 3 → 5

① Find the group

kth = getKth(group_prev, k); group_next = kth.next

D↑ group_prev→1→kth ↓2→group_next ↓3→4→5

k = 2 nodesrest of the list

Walk k steps from group_prev to reach kth. The node after it, group_next, starts the next group.

② Reverse the group (inner while loop)

prev, curr = group_next, group_prev.next → tmp = curr.next; curr.next = prev; prev = curr; curr = tmp

D⇢1←prev ↓2curr = group_next ↓3→4→5

1.next = group_next (3) (green arc) and 2.next = 1. The dummy still points to 1 (grey, old link) until we reconnect.

③ Reconnect and move group_prev

tmp = group_prev.next; group_prev.next = kth; group_prev = tmp

D↑ old group_prev→2→group_prev = tmp ↓1→3→4→5

D.next = kth (2). The old first node 1 is now the group's tail, so it becomes the new group_prev.

④ Second group: repeat with the new group_prev

kth = getKth(group_prev, k) → 4; group_next = kth.next → 5

D→2→1↑ group_prev→3→kth ↓4→group_next ↓5

k = 2 nodes

Same three moves again on nodes 3 and 4: reverse them so 3 → 5 and 4 → 3, then set group_prev.next = kth (1 → 4).

⑤ Reverse 3, 4 → reconnect → stop

getKth(group_prev, k) returns None (only node 5 left) → break; return dummy.next

D→return dummy.next ↓2→1→4→3↑ group_prev→5

Only node 5 is left, fewer than k, so getKth returns None and the loop breaks. Result: 2 → 1 → 4 → 3 → 5.

group being reversedalready reverseduntouched nodedummy (D = 0)green arrow = new link · grey dashed = old link

Python Solution

def reverseKGroup(head: Optional[ListNode], k: int) -> Optional[ListNode]:
    def getKth(curr, k):
        while curr and k > 0:
            curr = curr.next
            k -= 1
        return curr

    dummy = ListNode(0, head)
    group_prev = dummy

    while True:
        kth = getKth(group_prev, k)
        if not kth:
            break
        group_next = kth.next

        # Reverse the group; prev starts at group_next to link the tail
        prev, curr = group_next, group_prev.next
        while curr != group_next:
            tmp = curr.next
            curr.next = prev
            prev = curr
            curr = tmp

        # Reconnect: old first node is now the group's tail
        tmp = group_prev.next
        group_prev.next = kth
        group_prev = tmp

    return dummy.next

K. V. Jobin