Pairwise Swap Elements of a Singly Linked List

Riya
Last Updated: May 13, 2022

Introduction-  

This article will discuss the problem of finding the problem “Pairwise Swap Elements of a Singly Linked List” and its solution. Before jumping into the details of the problem and approach to solve it, you need to know about the linked list data structure.

Now, let’s understand the problem. In this problem, a singly linked list is given, and we have to pairwise swap elements of the given linked list.

Let’s make it clear by taking an example-

Assume the given linked list is : 1 -> 4 -> 5 -> 9 -> 8 -> 5 -> 2 -> NULL

After swapping pairwise, the given linked list will get changed int

 4 -> 1 -> 9 -> 5 -> 5 -> 8 -> 2 -> NULL

 

Note here that the number of elements is odd, so the last element ‘2’ can’t be paired with any other element and it won’t be swapped with any other element.

Iterative Solution Approach

We have been given a singly linked list and we have to pairwise swap elements of this given linked list. The idea is to start traversing the linked list from its first node and swap its data with the next node and then move to the node which is next to its next node to consider the next pair.

Let’s use the above example to understand run this algorithm:                                                                                 

Algorithm -

Step 1. Create a class ‘Node’ for creating the linked lists.

Step 2. Then create the function “pairwiseSwap()” to pairwise swap elements of a singly linked list, which will accept one parameter - pointer to the head node of the given linked list.

Step 3.  Initialize two node pointers to point the first node and second node of the liked list and using these node pointers traverse each pair of the given linked list and while traversing swap the data of the two nodes of each pair.

Step 4. Finally, after traversing all the possible pairs in the linked list, return the head node of the new linked list generated by the pairwise swapping.

 

C++ code:

 

#include <bits/stdc++.h>
using namespace std;

// Class for creating nodes of the linked list
class Node {
public:
int data;
Node* next;
Node(int val) {
this->data = val;
this->next = NULL;
}
};

// Function to print the linked list
void printList(Node* head)
  {
   Node* curr_node = head;
   while(curr_node != NULL)
     {
      if(curr_node->next == NULL) cout<< curr_node->data <<" ";
      else {
                cout<<curr_node->data<<" -> ";
      }
      curr_node = curr_node->next;
     }
   cout<<endl;
  }

// Function to pairwise swap elements of a linked list
void pairwiseSwap(Node* head)
 {
  Node* curr_node = head;
 
  while(curr_node != NULL)
  {
    Node* next_node = curr_node->next;
    if(next_node!=NULL) {
    swap(curr_node->data, next_node->data);
    curr_node = next_node->next;
    }
    else break;
  }
 }
int main()
{
Node* head = new Node(1);
head->next = new Node(4);
head->next->next = new Node(5);
head->next->next->next = new Node(9);
head->next->next->next->next = new Node(8);
head->next->next->next->next->next = new Node(5);
head->next->next->next->next->next->next = new Node(2);

cout<<"The given linked list is: "<<endl;
printList(head);

// Call the function to pairwise swap elements of a linked list
pairwiseSwap(head);
    
cout<<"The linked list after pairwise swapping is: "<<endl;
printList(head);
}

 

Output:
The given linked list is: 
1 -> 4 -> 5 -> 9 -> 8 -> 5 -> 2 
The linked list after pairwise swapping is: 
4 -> 1 -> 9 -> 5 -> 5 -> 8 -> 2 

 

Algorithm Complexity: 

Time Complexity: O(N)

In the function “pairwise Swap()” created to pairwise swap elements of a linked list, we have created a “while loop” to traverse all the nodes of the given linked list. So, the time complexity is O(N), where ‘N’ is the number of nodes in the given linked list.

 

Space Complexity: O(1) 

As we have used constant space, so the space complexity is O(1)

 

Recursive Solution Approach

The idea behind this approach is the same as the previous approach. But here instead of traversing iteratively one by one each pair, we will call a recursive function. The recursive function will swap the data of the current node and its next node and then if a next pair exists, then the function will call itself for the next pair. In this way, the function will keep calling itself recursively up to the last possible pair in the linked list.

                                                                                        

Algorithm -

Step 1. Create a class ‘Node’ for creating the linked lists.

Step 2. Then create the recursive function “pairwiseSwap()” to pairwise swap elements of a linked list recursively, which will accept one parameter - pointer to the head node of the given linked list.

Step 3.  If the head node and its next node are not NULL, then swap their elements and recursively call the function for the next pair.

Step 4. Finally, after all the recursive calls, print the linked list generated by pairwise swapping.

 

C++ code:

 

#include <bits/stdc++.h>
using namespace std;

// Class for creating nodes of the linked list
class Node {
public:
int data;
Node* next;
Node(int val) {
this->data = val;
this->next = NULL;
}
};

// Function to print the linked list
void printList(Node* head)
  {
   Node* curr_node = head;
   while(curr_node != NULL)
     {
      if(curr_node->next == NULL) cout<< curr_node->data <<" ";
      else {
          cout<<curr_node->data<<" -> ";
      }
      curr_node = curr_node->next;
     }
   cout<<endl;
  }

// Recursive function to pairwise swap elements of a linked list
void pairwiseSwap(Node* head)
 {
  if(head != NULL and head->next !=NULL)
    {
     swap(head->data, head->next->data);
     pairwiseSwap(head->next->next);
    }
 }
int main()
{
Node* head = new Node(1);
head->next = new Node(4);
head->next->next = new Node(5);
head->next->next->next = new Node(9);
head->next->next->next->next = new Node(8);
head->next->next->next->next->next = new Node(5);
head->next->next->next->next->next->next = new Node(2);

cout<<"The given linked list is: "<<endl;
printList(head);

    // Call the function to pairwise swap elements
    pairwiseSwap(head);
    
    cout<<"The linked list after pairwise swapping is: "<<endl;
printList(head);
}

 

Output:
The given linked list is: 
1 -> 4 -> 5 -> 9 -> 8 -> 5 -> 2 
The linked list after pairwise swapping is: 
4 -> 1 -> 9 -> 5 -> 5 -> 8 -> 2 

 

Algorithm Complexity: 

Time Complexity: O(N)

The function “pairwiseSwap()”  created to pairwise swap elements, will be called for each pair of nodes and one call will take constant time. So, the time complexity is O(N).

 

Space Complexity: O(1) 

As we have used constant space, so the space complexity is O(1)

 

Frequently asked questions-

  1. What is a linked list?
    A linked list is a linear data structure that is formed by connected nodes. Each node has a value associated with it and the pointer(s) to its directly connected node(s).   
     
  2. What is the key difference between a singly linked list and a doubly-linked list?
     A singly-linked list is unidirectional, which means that the node of a singly linked list contains the pointer to its next node only. In contrast, a doubly-linked list is bidirectional, and its node contains the pointer to its next and previous nodes.
     
  3. Which approach iterative or recursive is better to be considered?

In the recursive function, function calls are stored in the stack and so if the number of nodes will be larger, we can get a “stack-overflow” error. Thus the iterative approach is better to be considered.

 

Key takeaways-

This article discussed the problem of finding the problem  “Pairwise Swap Elements of a Singly Linked List”, iterative and recursive approaches to solve the problem, their C++ implementation, and their time and space complexities. If you want to practice problems on a linked list, then you can visit codestudio.

 

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 ?
0 upvotes

Comments

No comments yet

Be the first to share what you think