Pairwise Swap Elements of a Singly Linked List

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

You can also try this code with Online C++ Compiler

Run Code

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)

Also Read - Selection Sort in C

Frequently Asked Questions

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

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.

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.

Conclusion

This article discussed the problem of finding the problem  “Pairwise Swap Elements of a Singly Linked List”, iterative and recursive approaches to solving 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 Coding Ninjas Studio.

Recommended Reading:

• Doubly Linked List
• Pairwise Swap elements of given Linked List by changing Links
• Pairwise swap adjacent nodes of a Linked list by changing pointers
• Difference between singly Linked List and Doubly Linked List
• Application of Linked Lists
• Recursive Selection sort for singly Linked Lists by Swapping Node Links
• Select a Random Node from a Linked List
• Partitioning a linked list around a given value and keeping the original order 
• Swap Nodes in Pairs

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.

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!