45.Reverse Nodes in K Group

HardLinked List · 11/11

Problem

Given the head of a linked list and a positive integer k, reverse the nodes of the list k at a time and return the modified list.

If the number of nodes left at the end is not a multiple of k, those final nodes stay in their original order. You may not change node values — only the nodes themselves (their next pointers) may be rearranged.

Examples

Input:  head = [1, 2, 3, 4, 5], k = 2
Output: [2, 1, 4, 3, 5]
Explanation: Groups [1,2] and [3,4] are reversed; [5] is shorter than k and stays.

Input:  head = [1, 2, 3, 4, 5], k = 3
Output: [3, 2, 1, 4, 5]
Explanation: Only [1,2,3] forms a full group; [4,5] is left as is.

Constraints

The number of nodes in the list is n.
1 <= k <= n <= 5000
0 <= Node.val <= 1000
Follow-up: solve it with O(1) extra memory.

💡 Key Insight

Each group is just the classic "reverse a linked list" applied to k nodes, plus careful reconnection: the node before the group (groupPrev) must point to the group's new first node, and the group's new last node (its old first) must point to whatever follows the group. Before reversing, walk k steps ahead to confirm a full group exists — that check is what leaves the short tail untouched. A dummy node makes the first group identical to every other.

Brute Force (Stack of Nodes)

TimeO(n)SpaceO(k)

Intuition

A stack reverses order for free. Push k nodes; if you managed to push all k, pop them and append in reversed order. If you hit the end before k, the leftover nodes are appended unchanged.

Algorithm

dummy, tail = dummy, curr = head.
Loop:
- Push up to k nodes from curr onto a stack, advancing curr.
- If the stack has fewer than k nodes, attach tail.next = groupStart (unchanged) and stop.
- Otherwise pop each node and append it to tail.
Set tail.next = curr after each full group so the list stays connected; return dummy.next.

Visualization

1 -> 2 -> 3 -> 4 -> 5, k = 2
push 1,2 -> pop 2,1   result: 2 -> 1
push 3,4 -> pop 4,3   result: 2 -> 1 -> 4 -> 3
push 5   -> only 1 < k, attach 5 as is
result: 2 -> 1 -> 4 -> 3 -> 5

Code

java

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        ListNode curr = head;
        Deque<ListNode> stack = new ArrayDeque<>();
        while (curr != null) {
            ListNode groupStart = curr;
            while (curr != null && stack.size() < k) {
                stack.push(curr);
                curr = curr.next;
            }
            if (stack.size() < k) {
                tail.next = groupStart; // short tail: keep original order
                return dummy.next;
            }
            while (!stack.isEmpty()) {
                tail.next = stack.pop();
                tail = tail.next;
            }
            tail.next = curr; // keep the list connected to the rest
        }
        return dummy.next;
    }
}

Complexity

Time: O(n) — every node is pushed and popped at most once.
Space: O(k) — the stack holds one group at a time.

Recursion

TimeO(n)SpaceO(n / k)

Intuition

Check whether the first k nodes exist. If they do, reverse just those k nodes, then the old head (now the group's tail) should point to the result of recursively processing the rest of the list.

Algorithm

Walk k nodes from head; if fewer than k, return head unchanged.
Reverse exactly k nodes starting from head, with prev initialised to reverseKGroup(kthNext, k) — so the reversed group is wired directly to the processed remainder.
Return prev (the new head of this group).

Visualization

reverseKGroup([1,2,3,4,5], 2)
  rest = reverseKGroup([3,4,5], 2)
           rest = reverseKGroup([5], 2) -> [5]   (fewer than k)
           reverse 3,4 onto [5] -> [4,3,5]
  reverse 1,2 onto [4,3,5] -> [2,1,4,3,5]

Code

java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // Check that a full group of k nodes exists
        ListNode probe = head;
        for (int i = 0; i < k; i++) {
            if (probe == null) {
                return head; // fewer than k nodes: leave as is
            }
            probe = probe.next;
        }
        // Reverse k nodes; the first node will end up pointing at the processed rest
        ListNode prev = reverseKGroup(probe, k);
        ListNode curr = head;
        for (int i = 0; i < k; i++) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev; // new head of this group
    }
}

Complexity

Time: O(n) — each node is checked and reversed a constant number of times.
Space: O(n / k) — one recursion frame per group.

Iterative In-Place ReversalOptimal

TimeO(n)SpaceO(1)

Intuition

Do the recursion's work left to right with a groupPrev pointer (the node just before the current group, initially a dummy). For each group: find the k-th node; if it does not exist, stop. Otherwise reverse the group with prev starting at kth.next (so the old first node automatically links to the next group), then hook groupPrev.next to kth and move groupPrev to the old first node.

Algorithm

dummy.next = head, groupPrev = dummy.
Loop:
- kth = getKth(groupPrev, k); if null, break.
- groupNext = kth.next.
- Reverse nodes from groupPrev.next up to groupNext with prev = groupNext.
- oldFirst = groupPrev.next; groupPrev.next = kth; groupPrev = oldFirst.
Return dummy.next.

Dry Run

head = [1,2,3,4,5], k = 2, first group:

flowchart LR
    D["dummy<br/>groupPrev"] --> N1["1"]
    N1 --> N2["2<br/>kth"]
    N2 --> N3["3<br/>groupNext"]
    N3 --> N4["4"]
    N4 --> N5["5"]

After reversing 1, 2 with prev = groupNext (3) and setting dummy.next = kth (2):

flowchart LR
    D["dummy"] --> N2["2"]
    N2 --> N1["1<br/>new groupPrev"]
    N1 --> N3["3"]
    N3 --> N4["4"]
    N4 --> N5["5"]

The second group 3, 4 is handled the same way. For the third, getKth from 3 finds only 5 and then null, so the loop stops and 5 stays put: 2 → 1 → 4 → 3 → 5.

Code

java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    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; // fewer than k nodes remain
            }
            ListNode groupNext = kth.next;

            // Reverse the group; the first node ends up pointing to groupNext
            ListNode prev = groupNext;
            ListNode curr = groupPrev.next;
            while (curr != groupNext) {
                ListNode next = curr.next;
                curr.next = prev;
                prev = curr;
                curr = next;
            }

            ListNode oldFirst = groupPrev.next; // becomes the group's last node
            groupPrev.next = kth;               // connect previous part to new first
            groupPrev = oldFirst;
        }
        return dummy.next;
    }

    // Returns the node k steps after curr, or null if the list is too short
    private ListNode getKth(ListNode curr, int k) {
        while (curr != null && k > 0) {
            curr = curr.next;
            k--;
        }
        return curr;
    }
}

Complexity

Time: O(n) — each node is visited by getKth once and reversed once.
Space: O(1) — only a constant number of pointers.

Complexity Comparison

Approach	Time	Space
Stack of Nodes	O(n)	O(k)
Recursion	O(n)	O(n/k)
Iterative In-Place Reversal	O(n)	O(1)

Common Pitfalls

Reversing the final short group — always confirm k nodes exist before reversing.
Initialising prev = null when reversing a group; the group's old first node then points to null and the rest of the list is lost. Start with prev = groupNext.
Forgetting to update groupPrev to the group's old first node (now its last), not to kth.
Swapping node values instead of relinking nodes — the problem explicitly forbids changing values.
In the stack version, not setting tail.next = curr after each group, which can leave a cycle back into the reversed nodes.