> For the complete documentation index, see [llms.txt](https://soumyajit4419.gitbook.io/ds-algo/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://soumyajit4419.gitbook.io/ds-algo/linked-list/20.-reverse-nodes-in-k-group.md).

# 20. Reverse Nodes in k-Group

IMP

Given a linked list, reverse the nodes of a linked list *k* at a time and return its 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.

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/10/03/reverse_ex1.jpg)

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

**Example 2:**

![](https://assets.leetcode.com/uploads/2020/10/03/reverse_ex2.jpg)

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

**Example 3:**

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

**Example 4:**

```
Input: head = [1], k = 1
Output: [1]
```

## Solution: 

**Approach:**

**Adding a prenode and changing 3 pointers**

```
-1 -> 1 -> 2 -> 3 -> 4 -> 5
 |    |    |    | 
pre  cur  nex  tmp

-1 -> 2 -> 1 -> 3 -> 4 -> 5
 |         |    |    | 
pre       cur  nex  tmp

-1 -> 3 -> 2 -> 1 -> 4 -> 5
 |              |    |    | 
pre            cur  nex  tmp
```

```cpp
struct ListNode {
      int val;
     ListNode *next;
      ListNode() : val(0), next(nullptr) {}
      ListNode(int x) : val(x), next(nullptr) {}
      ListNode(int x, ListNode *next) : val(x), next(next) {}
  };
 
class Solution
{
public:
    ListNode *reverseKGroup(ListNode *head, int k)
    {

        if (head == NULL || k == 1)
        {
            return head;
        }
        ListNode *p = head;
        int count = 0;
        while (p != NULL)
        {
            p = p->next;
            count++;
        }
        ListNode *prenode = new ListNode;
        prenode->val = -1;
        prenode->next = head;
        ListNode *pre = prenode;
        ListNode *cur = prenode;
        ListNode *nxt = prenode;
        ListNode *temp = NULL;

        while (count >= k)
        {
            cur = pre->next;
            nxt = cur->next;

            for (int i = 1; i < k; i++)
            {
                temp = nxt->next;
                nxt->next = pre->next;
                pre->next = nxt;
                cur->next = temp;
                nxt = temp;
            }
            count -= k;
            pre = cur;
        }

        return prenode->next;
    }
};
```

**Time Complexity: O(n)**\
**Space Complexity: O(1)**