Reverse Nodes in K-Group


Difficulty Level Hard
Frequently asked in Adobe Amazon Apple ByteDance Facebook Microsoft
Linked-List

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

Output

[ 3, 2, 1, 5, 4]

Explanation

Reverse Nodes in K-Group

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; 

/* Link list node */
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* current = head; 
  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) 
  head->next = reverse(next, k); 

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

/* UTILITY FUNCTIONS */
/* Function to push a node */
void push(Node** head_ref, int new_data) 
{ 
  /* allocate node */
  Node* new_node = new Node(); 

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

  /* link the old list off the new node */
  new_node->next = (*head_ref);	 

  /* move the head to point to the new node */
  (*head_ref) = new_node; 
} 

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

int main() 
{
  Node* head = NULL; 

  /* Created Linked list is 1->2->3->4->5->6->7->8->9 */
  push(&head, 9); 
  push(&head, 8); 
  push(&head, 7); 
  push(&head, 6); 
  push(&head, 5); 
  push(&head, 4); 
  push(&head, 3); 
  push(&head, 2); 
  push(&head, 1);	 

  cout<<"Given linked list \n"; 
  printList(head); 
  head = reverse(head, 3); 

  cout<<"\nReversed Linked list \n"; 
  printList(head); 

  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 LinkedList 
{ 
  Node head; // head of list 

  /* Linked list Node*/
  class Node 
  { 
    int data; 
    Node next; 
    Node(int d) {data = d; next = null; } 
  } 

  Node reverse(Node head, int k) 
  { 
  Node current = head; 
  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) 
    head.next = reverse(next, k); 

  // 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 */
    new_node.next = head; 

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

  /* Function to print linked list */
  void printList() 
  { 
    Node temp = head; 
    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[]) 
  { 
    LinkedList llist = new LinkedList(); 
    
    /* 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); 
    
    System.out.println("Given Linked List"); 
    llist.printList(); 
    
    llist.head = llist.reverse(llist.head, 3); 

    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