# Reverse Linked List in groups of Size K

In this article, we will solve a very popular question Reverse Linked List in groups of Size K.

Problem Statement: 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.

Note: Also check this article to reverse a linked list

Examples:

```Example 1:
Input:
head = [1,2,3,4,5,6,7,8] k=3
Output:
Explanation: ```
```Example 2:
Input:
head = [1,2,3,4,5,6,7,8] k=2
Output:
Explanation: ```

Solution:

Approach:

The following steps are needed to arrive at the desired output.

• Create a dummy node. Point next to this node to head of the linked list provided.
• Iterate through the given linked list to get the length of the list.
• Create three pointer pre,cur and nex to reverse each group. Why? If we observe output, we can see that we have to reverse each group, apart from modifying links of group.
• Iterate through the linked list until the length of list to be processed is greater than and equal to given k.
• For each iteration, point cur to pre->next and nex to nex->next.
• Start nested iteration for length of k.
• For each iteration, modify links as following steps:-
• cur->next = nex->next
• nex->next = pre->next
• pre->next = nex
• nex = cur->next
• Move pre to cur and reduce length by k.

Dry Run:

Code:

## C++ Code

``````#include<bits/stdc++.h>
using namespace std;

class node {
public:
int num;
node* next;
node(int a) {
num = a;
next = NULL;
}
};
//utility function to insert node in the list
void insertNode(node* &head,int val) {
node* newNode = new node(val);
if(head == NULL) {
return;
}

node* temp = head;
while(temp->next != NULL) temp = temp->next;

temp->next = newNode;
return;
}
//utility function to find length of the list
int length = 0;
while(head != NULL) {
++length;
}
return length;
}
//utility function to reverse k nodes in the list
node* reverseKNodes(node* head,int k) {

node* dummyHead = new node(0);

node* pre = dummyHead;
node* cur;
node* nex;

while(length >= k) {
cur = pre->next;
nex = cur->next;
for(int i=1;i<k;i++) {
cur->next = nex->next;
nex->next = pre->next;
pre->next = nex;
nex = cur->next;
}
pre = cur;
length -= k;
}
}
//utility function to print the list
while(head->next != NULL) {
}
}

int main() {
node* head = NULL;
int k = 3;

cout<<"After Reversal of k nodes: ";

return 0;
}
``````

Output:

Original Linked List: 1->2->3->4->5->6->7->8
After Reversal of k nodes: 3->2->1->6->5->4->7->8

Time Complexity: O(N)

Reason: Nested iteration with O((N/k)*k) which makes it equal to O(N).

Space Complexity: O(1)

Reason: No extra data structures are used for computation.

## Java Code

``````import java.util.*;
class Node {
int num;
Node next;
Node(int a) {
num = a;
next = null;
}
}
class TUF{
//utility function to insert node in the list
static Node insertNode(Node head,int val) {
Node newNode = new Node(val);
if(head == null) {
}

Node temp = head;
while(temp.next != null) temp = temp.next;

temp.next = newNode;
}
//utility function to find length of the list
int length = 0;
while(head != null) {
++length;
}
return length;
}
//utility function to reverse k nodes in the list
static Node reverseKNodes(Node head,int k) {

Node dummyHead = new Node(0);

Node pre = dummyHead;
Node cur;
Node nex;

while(length >= k) {
cur = pre.next;
nex = cur.next;
for(int i=1;i<k;i++) {
cur.next = nex.next;
nex.next = pre.next;
pre.next = nex;
nex = cur.next;
}
pre = cur;
length -= k;
}
}
//utility function to print the list
while(head.next != null) {
}
}

public static void main(String args[]) {
Node head = null;
int k = 3;

System.out.print("Original Linked List: ");
System.out.print("After Reversal of k nodes: ");

}
}
``````

Output:

Original Linked List: 1->2->3->4->5->6->7->8
After Reversal of k nodes: 3->2->1->6->5->4->7->8

Time Complexity: O(N)

Reason: Nested iteration with O((N/k)*k) which makes it equal to O(N).

Space Complexity: O(1)

Reason: No extra data structures are used for computation.

Special thanks to Dewanshi Paul for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article