Problem Statement:
You are given a linked list and an integer k, you need to reverse it group wise.
Example
Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> NULL k =3
Output: 3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 8 -> 7 -> NULL
Solution
The solution is simple.
We reverse the first ‘k’ nodes. While reversing, we need to keep track of the next node and previous node.
“next” pointer is used to keep track of next node, “prev” pointer is used to keep track of previous node.
Then we recursively call head->next = reverse(), and we return “prev” that will become the new head of the list.
Solution in C++
#include <vector>
#include <algorithm>
//visit www.ProDeveloperTutorial.com for 450+ solved questions
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
#include <sstream>
using namespace std;
#include<iostream>
#include<vector>
using namespace std;
struct Node
{
int data;
struct Node* next;
};
void insert_at_begenning ( struct Node **head_pointer, int data)
{
// allocate memory for new node
struct Node *temp_node = (struct Node*) malloc(sizeof(struct Node));
// assign the data to new node
temp_node->data = data;
// initialize the new node to point to NULL
temp_node->next = NULL;
// if this is the first pointer, then this is the head pointer
if (*head_pointer == NULL)
{
*head_pointer = temp_node;
}
else
{
// point the next of the present pointer to the head pointer
temp_node->next = *head_pointer;
//then move the reference of head pointer to the current pointer
*head_pointer = temp_node;
}
}
void display_list(struct Node **head_pointer)
{
// take a reference to head pointer for navigation
struct Node *temp = *head_pointer;
while(temp != NULL)
{
if(temp->next != NULL)
printf("%d -> ", temp->data);
else
printf("%d", temp->data);
//navigate to next pointer
temp = temp->next;
}
printf("\n");
}
struct Node *reverse(struct Node *head, int k)
{
struct Node* curr = head;
struct Node* next = NULL;
struct Node* 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;
}
int main()
{
struct Node *list_1 = NULL;
struct Node *result = NULL;
int k = 2;
insert_at_begenning(&list_1,8);
insert_at_begenning(&list_1,7);
insert_at_begenning(&list_1,6);
insert_at_begenning(&list_1,5);
insert_at_begenning(&list_1,4);
insert_at_begenning(&list_1,3);
insert_at_begenning(&list_1,2);
insert_at_begenning(&list_1,1);
printf("Original Lis\n");
display_list(&list_1);
result = reverse(list_1, 2);
printf("The result list using recursive method is\n");
display_list(&result);
return 0;
}
Output:
Original List
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
The result list using recursive method is
2 -> 1 -> 4 -> 3 -> 6 -> 5 -> 8 -> 7