Reverse alternate K nodes in a Singly Linked List

Harsh Goyal
Last Updated: May 13, 2022

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.

 

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 

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);
}

 

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);
}

 

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)

Incall 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).

Frequently asked questions

1) What are the types of the Linked list?

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

 

2) What is the difference between Singly Linked List and 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. 

 

3) 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.

Key takeaways

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. 

If you think that this blog helped you, then share it with your friends!. Refer to the DSA C++ course for more information.
Until then, All the best for your future endeavors, and Keep Coding.

Was this article helpful ?
1 upvote

Comments

No comments yet

Be the first to share what you think