Reverse Nodes in k-Group

Companies:
  • Adobe Interview Questions
  • Amazon Interview Questions
  • Apple Interview Questions
  • ByteDance Interview Questions
  • Facebook Interview Questions
  • Microsoft Interview Questions

Problem Statement

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.

Sample Test Case

Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Problem Solution

We will approach this problem using recursion , we are asked to reverse nodes at a time, so what we are going to do is to reverse first nodes, then the second set of nodes and so on, until we reach the end of the list. So in each recursive call, we are going to make a k-time reversal and jump to the next round.

  1. Base case: The list has less than k nodes.
  2. Recursive Rules: 1) Recursively reverse the list beginning from k+1-th node. 2) Reverse the k nodes starting from current head, and connect the new reversed sub-list to the post result.

Reverse the first sub-list of size k. While reversing keep track of the next node and previous node. Let the pointer to the next node be next and pointer to the previous node be prev.

head->next = reverse(next, k) ( Recursively call for rest of the list and link the two sub-lists ).

Return prev prev becomes the new head of the list).

Complexity Analysis:

Time Complexity: O(n) Traversal of list is done only once and it has ‘n’ elements.

Auxiliary Space: O(1) No use of data structure for storing values.

Code Implementation

#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; 
    } 
} 

/* Driver code*/
int main() 
{ 
    /* Start with the empty list */
    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); 
}

 

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]