Home » Interview Questions » LinkedList Interview Questions » Reverse a Linked List in groups

Reverse a Linked List in groups


In the given linked list, write a function to reverse every set of k nodes.
(K is input value)



Time complexity : O(n)

a. Create a function ReverseInGroups to reverse the linked list in set of sub-lists of size k.

b. In this function, we use recursive method

      1) First reverse the first sub-list of size of k.

      2) Keep track of the next node(next) and previous nodes(previous).

      3) Function returns previous, which becomes the head of the list.

      4) For the rest of list call the recursive function and link the two sub-lists.

C++ Program

#include <bits/stdc++.h>

using namespace std;

struct LLNode
    int data;
    struct LLNode* next;

struct LLNode *reverse(struct LLNode *head, int k)
    struct LLNode* curr = head;
    //Initialize next and previous as null
    struct LLNode* next = NULL;
    struct LLNode* previous = NULL;
    int count = 0;   
    //reverse first k nodes
    while (curr != NULL && count < k)
        next  = curr->next;
        curr->next = previous;
        previous = curr;
        curr = next;
        count = count + 1;
    if (next !=  NULL)
       head->next = reverse(next, k); 
    //previous will be new head of the linked list
    return previous;
/* Function to insertAtBeginning a node */
void insertAtBeginning(struct LLNode** head, int dataToBeInserted)
    struct LLNode* curr = new LLNode;
    curr->data = dataToBeInserted;
    curr->next = NULL;    
    if(*head == NULL)
            *head=curr; //if this is first node make this as head of list
            curr->next=*head; //else make the curr (new) node's next point to head and make this new node a the head
        //O(1) constant time
//display linked list
void display(struct LLNode**node)
    struct LLNode *temp= *node;
            cout<<temp->data<<" ->";
            temp=temp->next; //move to next node
        //O(number of nodes)
//Main function
int main(void)

    struct LLNode* head = NULL;//initial list has no elements
    insertAtBeginning(&head, 9);
    insertAtBeginning(&head, 8);
    insertAtBeginning(&head, 7);
    insertAtBeginning(&head, 6);
    insertAtBeginning(&head, 5);
    insertAtBeginning(&head, 4);
    insertAtBeginning(&head, 3);
    insertAtBeginning(&head, 2);
    insertAtBeginning(&head, 1);           
    cout<<"The list initially is :-\n";
    int k = 3;
    cout<<"value of k: "<<k<<endl;
    head = reverse(head, k);//call function on head
    cout<<"\nFinal list after reversing is:-\n";


READ  Find Nth Node

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

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