Course4all
Join us on telegram
Home/dsa/Linked List Patterns/Reverse Nodes in k-Group

Reverse Nodes in k-Group

Master this topic with zero to advance depth.

Reverse Nodes in k-Group

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

List: 1 -> 2 -> 3 -> 4 -> 5, k = 3 1. Group [1,2,3] -> Reverse -> 3 -> 2 -> 1 2. Group [4,5] (Size 2 < 3) -> Keep 4 -> 5 Result: 3 -> 2 -> 1 -> 4 -> 5
Hard

Examples

Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]

The list is reversed in groups of size 2.

Approach 1

Level I: Recursive Approach

Intuition

We can solve the problem recursively by reversing the first k nodes and then calling the function recursively for the rest of the list.

⏱ O(N)💾 O(N/k) recursion stack

Detailed Dry Run

List: 1->2->3->4->5, k=2.

  1. First 2 nodes: 1->2. Reverse: 2->1.
  2. Recursive call on 3->4->5.
  3. Link 1 to the result of recursive call.
java
public ListNode reverseKGroup(ListNode head, int k) {
    ListNode curr = head;
    int count = 0;
    while (curr != null && count != k) {
        curr = curr.next;
        count++;
    }
    if (count == k) {
        curr = reverseKGroup(curr, k);
        while (count-- > 0) {
            ListNode tmp = head.next;
            head.next = curr;
            curr = head;
            head = tmp;
        }
        head = curr;
    }
    return head;
}

⚠️ Common Pitfalls & Tips

O(N/k) recursion stack space is used. The last group with < k nodes must be left as is.

Approach 2

Level II: Iterative with Stack

Intuition

Traverse the list and push k nodes onto a stack. If we have k nodes, pop them to reverse. If we reach the end with fewer than k nodes, append them as is.

Visual Trace

List: 1 -> 2 -> 3 -> 4, k=2 Iter 1: Stack=[1, 2]. Pop: 2 -> 1 Iter 2: Stack=[3, 4]. Pop: 4 -> 3 Result: 2 -> 1 -> 4 -> 3
⏱ O(N)💾 O(k)

Detailed Dry Run

List: 1->2->3, k=2. Stack=[1, 2], pop to get 2->1. Append 3.

java
public ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummy = new ListNode(0), tail = dummy, curr = head;
    while (curr != null) {
        Stack<ListNode> s = new Stack<>();
        ListNode tmp = curr;
        while (tmp != null && s.size() < k) {
            s.push(tmp);
            tmp = tmp.next;
        }
        if (s.size() == k) {
            while (!s.isEmpty()) {
                tail.next = s.pop();
                tail = tail.next;
            }
            tail.next = tmp;
            curr = tmp;
        } else {
            tail.next = curr;
            break;
        }
    }
    return dummy.next;
}
Approach 3

Level III: Optimal (Iterative Constant Space)

Intuition

To achieve O(1) space, we can iterate through the list and reverse the nodes in-place group by group. We use a dummy node to handle the head of the list properly.

⏱ O(N)💾 O(1)

Detailed Dry Run

Dummy -> 1 -> 2 -> 3 -> 4 -> 5, k=2.

  1. Reverse 1, 2: Dummy -> 2 -> 1 -> 3.
  2. Next group 3, 4: Dummy -> 2 -> 1 -> 4 -> 3 -> 5.
java
public ListNode reverseKGroup(ListNode head, int k) {
    if (head == null || k == 1) return head;
    ListNode dummy = new ListNode(0); dummy.next = head;
    ListNode curr = dummy, nxt = dummy, prev = dummy;
    int count = 0;
    while (curr.next != null) { curr = curr.next; count++; }
    while (count >= k) {
        curr = prev.next;
        nxt = curr.next;
        for (int i = 1; i < k; i++) {
            curr.next = nxt.next;
            nxt.next = prev.next;
            prev.next = nxt;
            nxt = curr.next;
        }
        prev = curr;
        count -= k;
    }
    return dummy.next;
}

⚠️ Common Pitfalls & Tips

Careful with pointer manipulations. Ensure the count check correctly stops when fewer than k nodes remain.

← Previous QuestionMerge K Sorted Lists
Next Question →Merge Two Sorted Lists