# Reverse Nodes in k-Group
**Difficulty:** HARD
[External](https://leetcode.com/problems/reverse-nodes-in-k-group)
Canonical: https://scaleengineer.com/dsa/problems/reverse-nodes-in-k-group
**Patterns:** [Recursion](https://scaleengineer.com/dsa/patterns/recursion)
**Data structures:** Linked List
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Infosys](https://scaleengineer.com/companies/infosys), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Nutanix](https://scaleengineer.com/companies/nutanix), [Qualcomm](https://scaleengineer.com/companies/qualcomm), [Snowflake](https://scaleengineer.com/companies/snowflake), [TikTok](https://scaleengineer.com/companies/tiktok), [VMware](https://scaleengineer.com/companies/vmware), [Visa](https://scaleengineer.com/companies/visa), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Yahoo](https://scaleengineer.com/companies/yahoo), [Capital One](https://scaleengineer.com/companies/capital-one), [Commvault](https://scaleengineer.com/companies/commvault), [Zopsmart](https://scaleengineer.com/companies/zopsmart), [josh technology](https://scaleengineer.com/companies/josh-technology), [MakeMyTrip](https://scaleengineer.com/companies/makemytrip), [PornHub](https://scaleengineer.com/companies/pornhub), [Tesla](https://scaleengineer.com/companies/tesla), [Zeta](https://scaleengineer.com/companies/zeta), [Autodesk](https://scaleengineer.com/companies/autodesk), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Arista Networks](https://scaleengineer.com/companies/arista-networks), [MathWorks](https://scaleengineer.com/companies/mathworks), [Sigmoid](https://scaleengineer.com/companies/sigmoid)
---
## Problem
Given the `head` of a linked list, reverse the nodes of the list `k` at a time, and return _the modified list_.

`k` is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of `k` then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list's nodes, only nodes themselves may be changed.

**Example 1:**

![](https://assets.glich.co/dsa/reverse-nodes-in-k-group/image0.jpg) 

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

**Example 2:**

![](https://assets.glich.co/dsa/reverse-nodes-in-k-group/image1.jpg) 

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

**Constraints:**

* The number of nodes in the list is `n`.
* `1 <= k <= n <= 5000`
* `0 <= Node.val <= 1000`

**Follow-up:** Can you solve the problem in `O(1)` extra memory space?

# Approaches
## Stack-Based Approach
This approach uses a stack to reverse nodes in groups of `k`. We iterate through the linked list, and for each group of `k` nodes, we push them onto a stack. Then, we pop the nodes from the stack and relink them in reversed order. This process is repeated until the end of the list is reached. If the last group has fewer than `k` nodes, it is left unchanged.
**Time:** O(N) · **Space:** O(k)
**Pros:** Conceptually simple and easy to understand.; Leverages a standard data structure.
**Cons:** Uses O(k) extra space, which is not optimal and fails the follow-up constraint.
### Explanation
This method provides a straightforward way to reverse the groups by leveraging the Last-In, First-Out (LIFO) property of a stack.

**Algorithm:**

1.  Create a `dummy` node that points to the `head` of the list. This simplifies handling the list's head.
2.  Initialize a `p` pointer to the `dummy` node. This pointer will track the end of the previously reversed group.
3.  Use a `while` loop to traverse the list. In each iteration, we first check if there are at least `k` nodes remaining.
4.  If a group of `k` nodes exists, push these `k` nodes onto a stack.
5.  Pop the nodes from the stack one by one and link them back into the list starting from `p.next`. Update `p` to point to the last node of the newly reversed group.
6.  The `next` of the new tail of the group should point to the start of the next group.
7.  If fewer than `k` nodes remain, the check at the beginning of the loop will fail, and we return the result.
8.  Return `dummy.next`.

```java
import java.util.Stack;

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || k == 1) return head;

        Stack<ListNode> stack = new Stack<>();
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode p = dummy;

        while (true) {
            ListNode check = p.next;
            int i = 0;
            for (; i < k; i++) {
                if (check == null) break;
                check = check.next;
            }
            if (i < k) break; // Not enough nodes

            ListNode temp = p.next;
            for (i = 0; i < k; i++) {
                stack.push(temp);
                temp = temp.next;
            }

            while (!stack.isEmpty()) {
                p.next = stack.pop();
                p = p.next;
            }
            p.next = temp;
        }
        return dummy.next;
    }
}
```
### Algorithm
- Create a `dummy` node pointing to `head` and a `prev` pointer to `dummy`.
- Create a stack to store nodes.
- Loop through the list:
  - First, check if there are `k` nodes available starting from `prev.next`.
  - If not, break the loop.
  - If yes, push the `k` nodes onto the stack.
  - Pop nodes from the stack and relink them. `prev.next` will point to the first popped node. Update `prev` after each pop.
  - After the group is reversed, link the tail of the reversed group to the start of the next group.
- Return `dummy.next`.

## Recursive Approach
This approach solves the problem by breaking it down into smaller, self-similar subproblems. The function reverses the first `k` nodes and then recursively calls itself on the rest of the list. The reversed group is then linked to the result of the recursive call.
**Time:** O(N) · **Space:** O(N/k)
**Pros:** Elegant and concise code.; Clearly separates the logic for one group from the rest.
**Cons:** The recursion stack uses O(N/k) space, which can be significant for small `k` and large `N`.; Not an O(1) space solution.
### Explanation
Recursion provides an elegant way to handle the linked structure of the problem. The main idea is to handle one group at a time and delegate the rest of the list to a recursive call.

**Algorithm:**

1.  Define a base case: if the list has fewer than `k` nodes, no reversal is needed, so return the current `head`. To check this, we can first iterate `k` nodes forward. If we hit `null`, we are in the base case.
2.  If there are at least `k` nodes, reverse the first `k` nodes of the list using the standard iterative reversal technique (with `prev`, `curr`, `next` pointers).
3.  After reversing, the original `head` of the group becomes the tail. The `next` pointer of this new tail should point to the result of the recursive call on the rest of the list (`reverseKGroup(next_node, k)`).
4.  The new head of the reversed group (which was the `k`-th node originally) is returned.

```java
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 1. Check if there are at least k nodes
        ListNode curr = head;
        int count = 0;
        while (curr != null && count < k) {
            curr = curr.next;
            count++;
        }

        // 2. If k nodes exist, reverse them
        if (count == k) {
            // Reverse the first k nodes
            ListNode prev = null;
            ListNode current = head;
            for (int i = 0; i < k; i++) {
                ListNode nextTemp = current.next;
                current.next = prev;
                prev = current;
                current = nextTemp;
            }

            // head is now the tail of the reversed group.
            // current is the head of the next part of the list.
            // Recursively call for the rest of the list and link.
            if (current != null) {
                head.next = reverseKGroup(current, k);
            }

            // prev is the new head of this reversed group
            return prev;
        } else {
            // 3. If less than k nodes, return head as is
            return head;
        }
    }
}
```
### Algorithm
- Check if the list contains at least `k` nodes. If not, return `head`.
- If it does, reverse the first `k` nodes of the list.
- The original `head` node will become the tail of the reversed group.
- Recursively call the function on the `(k+1)`-th node.
- Link the new tail's `next` pointer to the result of the recursive call.
- Return the new head of the reversed group.

## Iterative O(1) Space Approach
This is the most optimal approach, solving the problem iteratively with constant extra space. It processes the list in one pass, reversing each group of `k` nodes in place and carefully managing pointers to connect the reversed groups.
**Time:** O(N) · **Space:** O(1)
**Pros:** Most efficient solution with O(1) extra space.; Processes the list in a single pass without recursion.
**Cons:** The pointer manipulation can be complex and harder to reason about compared to the other approaches.
### Explanation
This method avoids both recursion and auxiliary data structures by using a few pointers to keep track of the different parts of the list during the reversal process.

**Algorithm:**

1.  Create a `dummy` node and point its `next` to `head`. This simplifies connections, especially for the first group.
2.  Initialize `groupPrev` to `dummy`. This pointer will always point to the node just before the current group being processed.
3.  Enter a loop that continues as long as there are full groups of `k` nodes to reverse.
4.  In each iteration, first find the `k`-th node of the current group. Let's call it `kth`. If `kth` is `null`, it means we have fewer than `k` nodes left, so we break the loop.
5.  Identify the start of the current group (`groupStart = groupPrev.next`) and the start of the next group (`nextGroupStart = kth.next`).
6.  Reverse the sublist from `groupStart` to `kth` in place. A common way is to treat `nextGroupStart` as the `prev` pointer's initial value in a standard reversal loop.
7.  After reversal, the old `kth` node is the new head of the group, and the old `groupStart` is the new tail.
8.  Connect the previous part of the list to this newly reversed group: `groupPrev.next = kth`.
9.  Update `groupPrev` to be the tail of the just-reversed group (`groupStart`) to prepare for the next iteration.
10. Return `dummy.next`.

```java
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || k == 1) {
            return head;
        }

        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode groupPrev = dummy;

        while (true) {
            // 1. Find the k-th node of the current group
            ListNode kth = groupPrev;
            for (int i = 0; i < k && kth != null; i++) {
                kth = kth.next;
            }

            // If we don't have k nodes, we are done
            if (kth == null) {
                break;
            }

            // 2. Identify pointers for reversal and connection
            ListNode groupStart = groupPrev.next;
            ListNode nextGroupStart = kth.next;

            // 3. Reverse the k nodes in place
            ListNode prev = nextGroupStart;
            ListNode current = groupStart;
            while (current != nextGroupStart) {
                ListNode nextTemp = current.next;
                current.next = prev;
                prev = current;
                current = nextTemp;
            }

            // 4. Connect the reversed group
            groupPrev.next = kth;

            // 5. Update groupPrev for the next iteration
            groupPrev = groupStart;
        }

        return dummy.next;
    }
}
```
### Algorithm
- Create a `dummy` node pointing to `head`.
- Initialize `groupPrev` to `dummy`.
- Loop through the list:
  - Find the `k`-th node of the current group, let's call it `kth`.
  - If `kth` is not found, break the loop.
  - Reverse the sublist between `groupPrev.next` and `kth`.
  - Connect `groupPrev.next` to the new head of the reversed group (the old `kth` node).
  - Update `groupPrev` to point to the tail of the reversed group (the old start of the group).
- Return `dummy.next`.

# Solutions
### CSharp

```csharp
/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val=0, ListNode next=null) { * this.val = val; * this.next = next; * } * } */ public class Solution { public ListNode ReverseKGroup ( ListNode head , int k ) { ListNode dummy = new ListNode ( 0 , head ); ListNode pre = dummy , cur = dummy ; while ( cur . next != null ) { for ( int i = 0 ; i < k && cur != null ; ++ i ) { cur = cur . next ; } if ( cur == null ) { return dummy . next ; } ListNode t = cur . next ; cur . next = null ; ListNode start = pre . next ; pre . next = ReverseList ( start ); start . next = t ; pre = start ; cur = pre ; } return dummy . next ; } private ListNode ReverseList ( ListNode head ) { ListNode pre = null , p = head ; while ( p != null ) { ListNode q = p . next ; p . next = pre ; pre = p ; p = q ; } return pre ; } }
```

### Java

```java
public class Reverse_Nodes_in_k_Group { class Solution { public ListNode reverseKGroup ( ListNode head , int k ) { ListNode dummy = new ListNode ( 0 ); dummy . next = head ; ListNode prev = dummy ; // count total nodes ListNode tmp = head ; int count = 0 ; while ( tmp != null ) { count ++; tmp = tmp . next ; } // 1->2->3->4->5 , k=3 // 2,1,3,4,5 // 3,2,1,4,5 // => always getting 1's next for prev's next => current (below) not changing in one-batch-swap // if only one node left, then no swap while ( count >= k ) { ListNode originalFirst = prev . next ; int kcopy = k - 1 ; // @note: since current node is already counted as 1 while ( kcopy > 0 ) { // both prev and current, not changed in while loop ListNode nextNextCopy = originalFirst . next . next ; ListNode firstInGroup = prev . next ; prev . next = originalFirst . next ; prev . next . next = firstInGroup ; originalFirst . next = nextNextCopy ; kcopy --; } // @note: update previous AND current. I forgot current... prev = originalFirst ; // now current is the last one of this group count -= k ; } return dummy . next ; } } } ////// /** * 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 pre = dummy , cur = dummy ; while ( cur . next != null ) { for ( int i = 0 ; i < k && cur != null ; ++ i ) { cur = cur . next ; } if ( cur == null ) { return dummy . next ; } ListNode t = cur . next ; cur . next = null ; ListNode start = pre . next ; pre . next = reverseList ( start ); start . next = t ; pre = start ; cur = pre ; } return dummy . next ; } private ListNode reverseList ( ListNode head ) { ListNode pre = null , p = head ; while ( p != null ) { ListNode q = p . next ; p . next = pre ; pre = p ; p = q ; } return pre ; } }
```

### Python

```python
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution : def reverseKGroup ( self , head : ListNode , k : int ) -> ListNode : ''' for reverse 1->2->3->4->5, process is like 1->None, 2->3->4->5 2->1->None, 3->4->5 3->2->1->None, 4->5 4->3->2->1->None, 5 5->4->3->2->1->None, None ''' def reverseList ( head ): pre , p = None , head while p : pnext = p . next p . next = pre pre = p p = pnext return pre dummy = ListNode ( next = head ) pre = cur = dummy while cur . next : for _ in range ( k ): cur = cur . next if cur is None : return dummy . next t = cur . next cur . next = None # cut from next k-group, so to reverseList() for current k-group start = pre . next pre . next = reverseList ( start ) start . next = t # so now 'start' is the last node of k-group pre = cur = start # same as the reset dummy before while loop return dummy . next ############ # Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution ( object ): def reverseKGroup ( self , head , k ): """ :type head: ListNode :type k: int :rtype: ListNode """ def reverseList ( head , k ): pre = None cur = head while cur and k > 0 : tmp = cur . next cur . next = pre pre = cur cur = tmp k -= 1 head . next = cur return cur , pre length = 0 p = head while p : length += 1 p = p . next if length < k : return head step = length / k ret = None pre = None p = head while p and step : next , newHead = reverseList ( p , k ) if ret is None : ret = newHead if pre : pre . next = newHead pre = p p = next step -= 1 return ret
```

### CPP

```cpp
// OJ: https://leetcode.com/problems/reverse-nodes-in-k-group/ // Time: O(N) // Space: O(1) class Solution { public: ListNode * reverseKGroup ( ListNode * head , int k ) { ListNode h , * tail = & h ; while ( head ) { auto prev = tail ; int i = 0 ; for ( auto p = head ; i < k && p ; ++ i , p = p -> next ); if ( i < k ) { tail -> next = head ; break ; } for ( int i = 0 ; i < k && head ; ++ i ) { auto node = head ; head = head -> next ; node -> next = prev -> next ; prev -> next = node ; } while ( tail -> next ) tail = tail -> next ; } return h . next ; } };
```