Hard java coding

How do you reverse a linked list in groups of k?

The 30 second answer

I put a dummy node before the head and keep a pointer to the node before the current group. For each group I first check that k nodes remain; if not, I leave the tail as it is. Then I reverse those k nodes with the usual three-pointer loop, starting prev at the node after the group so the reversed group stays connected, and move the group pointer to the old first node. O(n) time, O(1) space.

The plan. This is the iterative reverse applied to one window at a time, plus careful reconnection:

  1. groupPrev is the node just before the current group; a dummy node plays that role for the first group.
  2. Walk k steps from groupPrev to find kth, the last node of the group. If the list ends first, stop: the common version of this problem leaves a final group shorter than k unchanged.
  3. Reverse the group, starting prev at groupNext (the node after the group), so the old first node ends up pointing at the rest of the list.
  4. Link groupPrev.next to kth, the group's new first node, and move groupPrev to the old first node, now the group's last.
// Reverse every full group of k; a final group shorter than k stays as it is.
static Node reverseKGroup(Node head, int k) {
    if (k <= 1) return head;
    Node dummy = new Node(0, head), groupPrev = dummy;
    while (true) {
        Node kth = groupPrev;
        for (int i = 0; i < k && kth != null; i++) kth = kth.next;
        if (kth == null) break;              // fewer than k nodes left
        Node groupNext = kth.next;
        Node prev = groupNext, curr = groupPrev.next;
        while (curr != groupNext) {          // reverse this group in place
            Node next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        Node oldFirst = groupPrev.next;      // becomes the last node of the group
        groupPrev.next = kth;                // kth is the group's new first node
        groupPrev = oldFirst;
    }
    return dummy.next;
}
// reverseKGroup(of(1,2,3,4,5), 2)   -> [2,1,4,3,5]
// reverseKGroup(of(1,2,3,4,5), 3)   -> [3,2,1,4,5]
// reverseKGroup(of(1,2,3,4,5,6), 3) -> [3,2,1,6,5,4]
// reverseKGroup(of(1,2), 3)         -> [1,2]

Complexity. Each node is visited twice, once while counting k and once while reversing, so O(n) time, with O(1) extra space.

Clarify before coding. Ask what happens to a final group shorter than k (unchanged here; some variants reverse it too) and whether k can be 1 or larger than the list. Draw one group on paper before typing: almost every bug in this problem is a lost or misconnected pointer at a group boundary.

Sources (1)
  1. LeetCode 25: Reverse Nodes in k-Groupleetcode.com