# Reverse Nodes in K-Group

Difficulty Level Hard

## Problem

In Reverse Nodes in K-Group problem we have given a linked list, Reverse the linked list in a group of k and return the modified list.

If the nodes are not multiple of k then reverse the remaining nodes. The value of k is always smaller or equal to the length of the linked list and it is always greater than 0.

## Example

### Input

[ 1, 2, 3, 4, 5]  K=3

[ 3, 2, 1, 5, 4]

### Explanation We will reverse nodes in a group of k. As a value of k =3. So we will reverse first k nodes. The nodes are not a multiple of k so we are left with 2 nodes. We will reverse the remaining two nodes this is our answer.

## Approach for Reverse Nodes in K-Group

We will use a recursive approach to reverse the given linked list in a group of k.

• Reverse the first k nodes of the linked list. While reversing the first k nodes of the list maintain previous and next pointer. The previous pointer will point to the first node of the k-group nodes that we are reversing. The next pointer will point to the next node after the k-group node that we are reversing.
• After reversing the k-group nodes the recursive function will return the head of the k-group reversed node. So we will assign head->next=reverse(next, k).
• next is now pointing to the k+1th node. We will recursively call for the list starting from the current and will make the rest of the list as next to the first node.
• After all the recursive operation we will get a linked list which is formed after performing the reverse operation in a group of k nodes.

## Implementation for Reverse Nodes in K-Group

### C++ code for Reverse Nodes in K-Group

```// CPP program to reverse a linked list
// in groups of given size
#include <bits/stdc++.h>
using namespace std;

class Node
{
public:
int data;
Node* next;
};

/* Reverses the linked list in groups
of size k and returns the pointer
to the new head node. */
Node *reverse (Node *head, int k)
{
Node* next = NULL;
Node* prev = NULL;
int count = 0;

/*reverse first k nodes of the linked list */
while (current != NULL && count < k)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
count++;
}

/* next is now a pointer to (k+1)th node
Recursively call for the list starting from current.
And make rest of the list as next of first node */
if (next != NULL)

/* prev is new head of the input list */
return prev;
}

/* UTILITY FUNCTIONS */
/* Function to push a node */
{
/* allocate node */
Node* new_node = new Node();

/* put in the data */
new_node->data = new_data;

/* link the old list off the new node */

/* move the head to point to the new node */
}

/* Function to print linked list */
void printList(Node *node)
{
while (node != NULL)
{
cout<<node->data<<" ";
node = node->next;
}
}

int main()
{

/* Created Linked list is 1->2->3->4->5->6->7->8->9 */

return(0);
}```
```Given Linked List
1 2 3 4 5 6 7 8 9
Reversed list
3 2 1 6 5 4 9 8 7```

### Java code for Reverse Nodes in K-Group

```// Java program to reverse a linked list in groups of
// given size
{

class Node
{
int data;
Node next;
Node(int d) {data = d; next = null; }
}

{
Node next = null;
Node prev = null;

int count = 0;

/* Reverse first k nodes of linked list */
while (count < k && current != null)
{
next = current.next;
current.next = prev;
prev = current;
current = next;
count++;
}

/* next is now a pointer to (k+1)th node
Recursively call for the list starting from current.
And make rest of the list as next of first node */
if (next != null)

// prev is now head of input list
return prev;
}

/* Utility functions */

/* Inserts a new Node at front of the list. */
public void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);

/* 3. Make next of new Node as head */

/* 4. Move the head to point to new Node */
}

/* Function to print linked list */
void printList()
{
while (temp != null)
{
System.out.print(temp.data+" ");
temp = temp.next;
}
System.out.println();
}

/* Driver program to test above functions */
public static void main(String args[])
{

/* Constructed Linked List is 1->2->3->4->5->6->
7->8->8->9->null */
llist.push(9);
llist.push(8);
llist.push(7);
llist.push(6);
llist.push(5);
llist.push(4);
llist.push(3);
llist.push(2);
llist.push(1);

llist.printList();

System.out.println("Reversed list");
llist.printList();
}
}```
```Given Linked List
1 2 3 4 5 6 7 8 9
Reversed list
3 2 1 6 5 4 9 8 7```

## Time complexity

O(n)  as each node is traversed only once.

## Space complexity

O(1) as we are using only variables to store the address of prev and next nodes.

References

Translate »