Linked List: Reverse Linked List in groups

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

 

 

 

 

Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *