# Reverse a Linked List in groups

0
286

## Algorithm

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)
{
//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)
{
}

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;
*head=curr; //if this is first node make this as head of list

else
{
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
}

void display(struct LLNode**node)
{
struct LLNode *temp= *node;
while(temp!=NULL)
{
if(temp->next!=NULL)
cout<<temp->data<<" ->";
else
cout<<temp->data;

temp=temp->next; //move to next node
}
//O(number of nodes)
cout<<endl;
}
//Main function
int main(void)
{

struct LLNode* head = NULL;//initial list has no elements