Reverse a Linked List in group of Given Size

The problem, simply

You get a linked list and a number k. Walk the chain in groups of k boxes. Turn each group around, but keep the groups themselves in their old order.

If the last group has fewer than k boxes, leave it as it is. Give back the new first box.

There is a second version of this problem (the GeeksforGeeks one) where the short last group is turned around too. The code changes in one line, shown in "Watch out for".

A story to remember it

Picture it

Examples

Way 1: the simple way

Let a helper handle the rest of the chain. This is recursion.

1. Check that there are at least k boxes from head. If not, return head unchanged.
2. Turn the first k boxes around with the three fingers prev, curr, next.
3. The old first box is now the end of this group. Hook it to whatever the helper returns for the rest of the chain.
4. Return the new first box of this group.

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode probe = head;
        for (int i = 0; i < k; i++) {          // are there k boxes?
            if (probe == null) return head;    // short group: leave it
            probe = probe.next;
        }
        ListNode prev = null, curr = head;
        for (int i = 0; i < k; i++) {          // turn this group around
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        head.next = reverseKGroup(curr, k);    // old first box hooks to the rest
        return prev;                           // new first box of this group
    }
}

How long it takes: every box is counted once and flipped once, O(n). Extra room: one waiting helper per group on the call stack, O(n/k). For a long chain and a small k, that stack can get deep.

Way 2: the clever way

Do the same with a loop and a fake box in front, the dummy. The finger groupPrev always sits on the box just before the group we are about to flip.

1. Put a dummy box D before the head. groupPrev = D.
2. Walk k steps from groupPrev to find kth, the last box of the group. If you fall off the chain, stop.
3. Remember groupNext = kth.next, the first box after the group.
4. Flip the group with prev starting at groupNext, so the old first box ends up pointing to groupNext.
5. Hook groupPrev.next = kth (the new first box), and move groupPrev to the old first box (the new last box).
6. Repeat. The answer is D.next.

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0, head);
        ListNode groupPrev = dummy;
        while (true) {
            ListNode kth = groupPrev;
            for (int i = 0; i < k && kth != null; i++) kth = kth.next;  // find the group's last box
            if (kth == null) break;                                    // short group: done

            ListNode groupNext = kth.next;
            ListNode prev = groupNext, curr = groupPrev.next;          // flip inside the group
            while (curr != groupNext) {
                ListNode next = curr.next;
                curr.next = prev;
                prev = curr;
                curr = next;
            }
            ListNode oldFirst = groupPrev.next;
            groupPrev.next = kth;          // hook the new first box
            groupPrev = oldFirst;          // the old first box is now the group's end
        }
        return dummy.next;
    }
}

How long it takes: each box is stepped over once when counting and once when flipping, O(n). Extra room: a handful of fingers and one dummy box, O(1).

Watch out for

• Starting prev at null inside a group cuts the chain. Start it at groupNext so the flipped group stays hooked to the rest.
• Moving groupPrev to kth. After the flip, kth is the front of the group. groupPrev must go to the old first box, the new back.
• The other version (turn the short last group around too): in Way 1, drop the "are there k boxes" check and flip while curr != null for at most k steps. In Way 2, when kth is null, flip the leftover boxes once and stop.
• k of 1 or an empty chain: both ways return the chain unchanged.

What interviewers ask next

• Swap nodes in pairs (LeetCode 24). It is this problem with k = 2.
• Reverse only between positions m and n (LeetCode 92). Walk to box m - 1, then flip one group of size n - m + 1 the same way.
• Reverse alternate groups: flip a group of k, then skip the next k boxes, and repeat. Add a skip loop after each hook.
• Why is the iterative way better in production? No deep call stack, so a chain of a million boxes with k = 2 does not overflow.
• What about a doubly linked list? Same groups, but inside a group you swap prev and next, and you also fix the prev of the box after each group.

Remember this

Grown-up words: the wagons are nodes, flipping is reversing the next pointers, the fake front wagon is a dummy node, and the helpers waiting on each other are the recursion call stack.