LeetCode 25 · Hard · Linked List

Reverse Nodes in k-Group

Reverse the nodes of a linked list k at a time and return the new head. A final group shorter than k stays in its original order. Relink the nodes; do not change their values.

O(n)time
O(1)space
groupPrevstitch each reversed block

1–10 integers, −99 to 99 · k from 1 to the list length

Linked list dashed = dummy · row 2 = the group being reversed · green = finished groups

public ListNode reverseKGroup(ListNode head, int k) { ListNode dummy = new ListNode(0, head); ListNode groupPrev = dummy; while (true) { ListNode kth = getKth(groupPrev, k); if (kth == null) { break; } ListNode groupNext = kth.next; ListNode prev = kth.next; ListNode curr = groupPrev.next; while (curr != groupNext) { ListNode tmp = curr.next; curr.next = prev; prev = curr; curr = tmp; } ListNode tmp = groupPrev.next; // old first, new last groupPrev.next = kth; groupPrev = tmp; } return dummy.next;}private ListNode getKth(ListNode curr, int k) { while (curr != null && k > 0) { curr = curr.next; k--; } return curr;}
groupPrev
—
kth
—
prev · curr
—
list
—

Why it works

  1. Brute force copies: push values k at a time onto a stack and pop them back out, or collect nodes into an array and relink. O(n) time, but O(n) or O(k) extra space and more bookkeeping.
  2. Each group is Reverse Linked List with fixed ends. Starting prev at groupNext (not null) makes the group's old first node point straight at the rest of the list when it flips. Then groupPrev.next = kth hooks the reversed block in from the front.
  3. O(n) time, O(1) space: getKth scans each node once ahead of the reversal, and the reversal touches each node once, so every node is visited about twice.
  4. Pitfall: check before you reverse. getKth returns null when fewer than k nodes remain, and the loop stops. Reversing first and undoing later is messier and wrong if you forget to undo.
  5. Pitfall: the old first node is the new last. Save it (tmp = groupPrev.next) before rewiring, because it becomes the next group's groupPrev. The dummy plays that role for the first group.
  6. Related: Reverse Linked List II (92) reverses one sublist between two positions with the same prev / curr loop and fixed ends.