Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Iterative Solution Approach
2.1.
Algorithm
2.2.
C++ Code
2.3.
Algorithm Complexity
3.
Recursive Solution Approach
3.1.
Algorithm
3.2.
C++ code
3.3.
Algorithm Complexity
4.
Frequently Asked Questions
4.1.
What is a linked list?
4.2.
What is the key difference between a singly linked list and a doubly-linked list?
4.3.
Which approach iterative or recursive is better to be considered?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Pairwise Swap Elements of a Singly Linked List

Riya
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

## 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 solving 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)

Recommended Topic, Floyds Algorithm

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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

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:

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!

Live masterclass