Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Brute Force Approach
2.1.
Algorithm
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
Optimized Approach
3.1.
Algorithm
3.2.
Implementation in C++
3.2.1.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What are the types of Linked lists?
4.2.
What is the difference between a Singly Linked List and a Doubly Linked List?
4.3.
What is the Circular Linked List?
5.
Conclusion
Last Updated: Mar 27, 2024

Reverse alternate K nodes in a Singly Linked List

Author Harsh Goyal
1 upvote
Linked List

Introduction

This blog will discuss the various approaches to solve the Reverse alternate K nodes in a Singly linked list problem. Before jumping into the problem of getting the Reverse alternate K nodes in a Singly Linked List, let’s first understand a Linked list.

A Linked list is a kind of data structure in which the elements are connected using pointers, and each node has the address of the pointer of its next node.

 

Singly Linked List

In this Reverse alternate K nodes in a Singly Linked List problem, we need to return the head of the linked list after reversing all the alternate k nodes.

You can refer to this link for more information on the linked list.

For Example:-

List :- 10 -> 15 -> 45 -> 17 -> 145 -> 125 -> 5 -> 11 -> 47 -> 43 -> 1 -> 75 , and K = 3

Output :- 45 -> 15 -> 10 -> 17 -> 145 -> 125 -> 47 -> 11 -> 5 -> 43 -> 1 -> 75 

Recommended Topic, Floyds Algorithm

Brute Force Approach

Brute Force Solution considers reversing the first ‘K’ nodes and iterating the pointer ‘K’ indexes forward, and then making a recursive call to reverse the next ‘K’ nodes. In this approach, the recursive call will be decided using a boolean variable. 

Algorithm

Step 1. Create a function ‘getResult()’ that will accept three parameters, i.e., one head pointer of the linked list, one variable ‘K’, and one boolean variable ‘x’, initially ‘x’ is true.

Step 2. Check if ‘X’ is true, then we have to reverse the first ‘K’ nodes by calling the recursive function ‘getResult()’.

Step 3. Check if ‘X’ is false, then we have to iterate our pointer and jump to the node at a distance ‘K’ from that node.

Step 4. We need to call the recursive function ‘getResult()’ and repeat the process for the remaining nodes and link the resultant list with the tail of the first ‘K’ nodes modified initially.

Step 5. Return the ‘head’ of the resultant modified, linked list.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
class Node
{
        public:
        int data;
        Node *next;
        Node(int data)
        {
                this->data = data;
                this->next = NULL;
            }
};

Node *takeinput()
{
    int data;
    cin >> data;
    Node *head = NULL, *tail = NULL;
    while (data != -1)
    {
        Node *newNode = new Node(data);
        if (head == NULL)
        {
            head = newNode;
            tail = newNode;
        }
        else
        {
            tail->next = newNode;
            tail = newNode;
        }
        cin >> data;
    }
    return head;
}

/* Function to print the linked list */
void print(Node *head)
{
    Node *temp = head;
    while (temp != NULL)
    {
        cout << temp -> data << " ";
        temp = temp -> next;
    }
    return;
} 
Node *getResult(Node *node, int k, bool x) 
{
    if (node == NULL) 
    {
        return NULL;
    }
 
    int count = 1;
    Node *prev = NULL;
    Node *temp = node;
    Node *next = NULL;
 
    while (temp != NULL && count <= k) 
    {
        next = temp -> next;
 
        /* Reverse the nodes only if x is true*/
        if (x == true) 
        {
            temp -> next = prev;
        }
 
        prev = temp;
        temp = next;
        count++;
    }
 
    if (x == true) 
    {
        node -> next = getResult(temp, k, !x);
        return prev;
    } 
    prev -> next = getResult(temp, k, !x);
    return node;
}

Node *reverse(Node *head, int k) 
{
    return getResult(head, k, true);
}

int main()
{
    Node *head = takeinput();
    cout << "Given Linked List:- " ;
    print(head);
    cout << endl;
    int k = 3;
    head = reverse(head, k);
    cout << "Modified Linked List:- " ;
    print(head);
}
You can also try this code with Online C++ Compiler
Run Code

 

Output :

Given Linked List:- 10 -> 15 -> 45 -> 17 -> 145 -> 125 -> 5 -> 11 -> 47 -> 43 -> 1 -> 75

Modified Linked List:-  45 -> 15 -> 10 -> 17 -> 145 -> 125 -> 47 -> 11 ->

Complexity Analysis

Time Complexity: O(N)

Incall to ‘getResult()’, we are working on ‘K’ nodes at one time, either it is the job of reversing the nodes or just traversing them, and in total, we are working on ‘’ nodes, therefore, the overall time complexity is O(N).

Space Complexity: O(N)

As we are using a linked list of size ‘N’, therefore, the overall space complexity will be O(N).

Optimized Approach

To optimize this Reverse alternate K nodes in a Singly Linked List problem, we’ll try to optimize the space used in the above approach, in this approach, we will try to cover a total of 2 * K nodes in a single iteration, and in this iteration, we’ll try to keep the record of first and last node of the single group of ‘K’ nodes. And after reversing the next group of ‘K’ nodes, we just need to join the recorded pointers to the new pointers of the reversed list.

Algorithm

Step 1. In the function call ‘getResult()’, it takes two parameters:- first will be the pointer to the head of the linked list, and the second will be the value of ‘K’. 

Step 2. Initialize a few variables as shown in the code, which are used in traversing and reversing the nodes.

Step 3. Initialize a variable ‘p’ used to keep the track of the count of the node.

Step 4. Make an iteration using the ‘while’ loop till the end of the linked list using ‘curr’ variable, and in this loop, use one more ‘while’ loop to reverse the alternate group of ‘K’ nodes and keep decrementing the value of ‘p’,and this ‘while’ loop will terminate if ‘curr’ is equal to null or ‘p’ is less than or equal to zero.

Step 5. Reverse the nodes using ‘temp’ and ‘curr’ nodes and assigning new value to ‘prev’ node.

Step 6. Update the new head using the ‘prev’.

Step 7. If the ‘tail’ node is not null then assign the value of the ‘prev’ node to the next pointer of the ‘tail’ node.

Step 8. Assign the value of ‘k’ to ‘p’.

Step 9. Now make an iteration using the ‘while’ loop to traverse ‘k’ nodes which are not meant to be reversed.

Step 10. After the termination of the outer ‘while’ loop, return the ‘head2’ node. 

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
class Node
{
        public:
        int data;
        Node *next;
        Node(int data)
        {
                this->data = data;
                this->next = NULL;
            }
};    

Node *takeinput()
{
    int data;
    cin >> data;
    Node *head = NULL, *tail = NULL;
    while (data != -1)
    {
        Node *newNode = new Node(data);
        if (head == NULL)
        {
            head = newNode;
            tail = newNode;
        }
        else
        {
            tail->next = newNode;
            tail = newNode;
        }
        cin >> data;
    }
    return head;
}

void print(Node *head)
{
    Node *temp = head;
    while (temp != NULL)
    {
        cout << temp -> data << " ";
        temp = temp -> next;
    }
    return;
}
   
Node *getResult(Node *head, int k)
{
    Node *prev = NULL;
    Node *curr = head;
    Node *temp = NULL;
    Node *tail = NULL;
    Node *head2 = NULL;
    Node *combine = NULL;
    
    // To track of counting
    int p = 0; 
    
    // Traverse the whole Linked-List
    while(curr) 
   {
       p = k;
       combine = curr;
       prev = NULL;
       
       // Reverse the group of alternate k nodes
       while(curr && p--) 
       {
         temp = curr->next;
         curr -> next = prev;
         prev = curr;
         curr = temp;
       }
      // update the new head
      if(head2==NULL)
      {
         head2=prev;
      }
      
      // the tail pointer has track of last node
      if(tail!=NULL)
      {
        tail->next=prev;
      }
      p = k; // update the count
      
      // Traverse whole without reversing
      while(curr && p--) 
      {
         prev = curr;
         curr= curr->next;
      }
      
      // Set tail to last pointer
      tail=prev;
    }
   return head2;
}
      
int main()
{
    Node *head = takeinput();
    cout << "Given Linked List:- " ;
    print(head);
    cout << endl;
    int k = 3;
    cout << "Value of K:- " << k << endl;
    head = getResult(head, k);
    cout << "Modified Linked List:- " ;
    print(head);
}
You can also try this code with Online C++ Compiler
Run Code

 

Output :

Given Linked List:- 10 -> 15 -> 45 -> 17 -> 145 -> 125 -> 5 -> 11 -> 47 -> 43 -> 1 -> 75

Modified Linked List:-  45 -> 15 -> 10 -> 17 -> 145 -> 125 -> 47 -> 11 -> 5 -> 43 -> 1 -> 75

Complexity Analysis

Time Complexity: O(N)

In call to ‘getResult()’, we are just traversing the whole linked list of size ‘N’ only once, therefore, the overall time complexity is O(N).

Space Complexity: O(1)

As we are using constant extra space, therefore, the overall space complexity is O(1).


Must Read  C Program to Reverse a Number

Frequently Asked Questions

What are the types of Linked lists?

A linked list is of three types:- Singly Linked List, Doubly Linked List, and Circular Linked List.

What is the difference between a Singly Linked List and a Doubly Linked List?

In Singly Linked List, each node has the address of the pointer to its next node, whereas, in Doubly Linked List, each node has the address of the pointers of its next node and its previous node. 

What is the Circular Linked List?

In Circular Linked List, the tail of the linked list points to the head of the same linked list.

Conclusion

In this article, we discussed the What is Reverse alternate K nodes in a Singly Linked List problem, discussed the various approaches to solving this problem programmatically, the time and space complexities, and how to optimize the approach by reducing the space complexity of the problem. 

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

To study more about Linked Lists, refer to Applications Of Linked Lists.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!

Live masterclass