Home » Technical Interview Questions » LinkedList Interview Questions » Reverse Nodes in K-Group

Reverse Nodes in K-Group


Reading Time - 6 mins

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.
READ  Add two numbers

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.

READ  Delete Nth node from the end of the given linked list

Space complexity

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

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions