Solution
Recommended: Please try to solve it yourself first before moving on to the solution.
The idea is simple:
- We will swap the nodes themselves instead of swapping the node values only.
- Change/Swap the pointers of the first two nodes and similarly swap the next two nodes until the end of the Linked List.
- Maintain a while loop and traverse the Linked List until the end by linking nodes in the swapped manner as mentioned in the above step.
Implementation in C++
#include<bits/stdc++.h>
using namespace std;
struct Node
{
int key;
struct Node *next;
};
// Function to perform the swap.
Node *pairWiseSwap(Node *root)
{
if (root == NULL || root->next == NULL)
return root;
Node *curr = root->next->next;
Node *prev = root;
root = root->next;
root->next = prev;
// Fix remaining nodes.
while (curr != NULL && curr->next != NULL)
{
prev->next = curr->next;
prev = curr;
Node *next = curr->next->next;
curr->next->next = curr;
curr = next;
}
prev->next = curr;
return root;
}
void push(struct Node** head, int data)
{
struct Node* node = new Node;
node->key = data;
node->next = (*head);
(*head) = node;
}
void print(struct Node *root)
{
while (root != NULL)
{
cout << root->key << " ";
root = root->next;
}
}
int main()
{
struct Node *head = NULL;
push(&head, 1);
push(&head, 2);
push(&head, 3);
push(&head, 4);
push(&head, 5);
push(&head, 6);
cout << "\n Linked List before ";
print(head);
head = pairWiseSwap(head);
cout << "\n Linked List after ";
print(head);
return 0;
}

You can also try this code with Online C++ Compiler
Run Code
Output:

Time Complexity: O(N)
Recursive Approach
The idea is to swap two nodes and recursively call the same function on the remaining nodes.
Implementation in C++
Node *pairWiseSwap(Node *head) {
if(!head || !head->next)
return head;
Node* newhead = head->next;
Node* next = newhead->next;
newhead->next = head;
head->next = pairWiseSwap(next);
return newhead;
}
}

You can also try this code with Online C++ Compiler
Run Code
Output:

Time Complexity: O(N)
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
Here we saw how to pairwise swap adjacent nodes of a Linked List by changing pointers.
Challenge: Can you solve it by swapping the node’s data instead of pointers?
Recommended Problems -
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.
Happy Coding!