Last Updated on November 18, 2022 by Prepbytes
In this article, we will understand how to pairwise swap elements of a linked list.
Linked list as a sequence of data structures which are connected through links and each node is having a pointer which points to the next node. let’s try how we can pairwise swap elements of a linked list.
Problem Statement
In this problem, we are given a linked list and we have to swap the elements in a pairwise manner. It is not allowed to swap the data, only links should be changed.
Let me explain pairwise swap of a linked list with an example – if the linked list is
then the function should change it to
Well, this is one of the most popular questions to be asked in interviews and may seem a bit difficult at first but it is easy to comprehend.
Problem Statement Understanding to pairwise swap elements of a linked list
Let’s first understand the problem statement with the help of an example.
Linked list = 1->2->3->4->5,
The term Pairwise swap indicates that we need to swap the positions of the adjacent two nodes in the linked list.
So,
- 1->2 will become 2->1
- 3->4 will become 4->3
- 5 has no one to be paired with hence it remains as it is.
Finally the linked list will be = 2->1->4->3->5.
Let’s take an example with an even-length linked list.
Linked list = 4->1->6->3->8->9
So performing the pairwise swap,
- 4->1 will become 1->4.
- 6->3 will become 3->6.
- 8->9 will become 9-8.
Finally the linked list will be = 1->4->3->6->9->8.
You should take more examples and get the output according to the above understanding to pairwise swap elements of a linked list. Analyzing different examples will help you create the logic for this question.
Approach to pairwise swap of linked list
I hope you got a basic idea on what we need to do to solve this question.
The idea is simple, we have to change the links of the nodes alternatively for every 2 nodes. We will traverse the linked list from the beginning and for every two nodes, we will change the pointers of the next nodes to the previous nodes.
Since it is clear what we need to do to pairwise swap elements of a linked list, take some time and think on how we are going to do it.
Helpful Observations
-
Since we need to swap two nodes, that is change the links, we should have two pointers pointing on the nodes.
-
Suppose linked list = &1->2->3->4,and two pointers be prev and curr.
- The prev pointing to the node(1) and curr pointing to the node(2).
- We can see that we need to change curr->next and point it to prev i.e 2->1.
- Also finally the linked list will be 2->1->4->3 i.e. the next of nodes with value 1 will point to the node with value 4, so that means prev->next should be curr->next->next. (Think why this step should be done before step 2).
- Step 3 should be done before Step 2 because we need to access node(4) from node(2) but in step 2, node(2)->next is changed to node(1), hence connection to node(4) is lost.
- Or we can simply store in temporary node node(2)->next and follow the above steps in given order.
-
There are some corner conditions to handle, take some examples, use the above observations and try to get those corner conditions.
-
Below is the proper algorithm to pairwise swap elements of a linked list.
Algorithm for a pairwise swap of a linked list
- Initialize prev and curr pointers.
- Traverse the list, store in the temp node the value of curr-> next and change the next of curr as of the prev node.
- If temp is NULL or temp is the last node then change prev-> next to NULL and break the iteration. (Above mentioned corner conditions).
- Else we have to change next of prev to next of curr.
- Update prev and curr nodes for the next iteration.
Code Implementation for a pairwise swap of a linked list
The most efficient way to Pairwise swap elements of a given linked list
#include <stdio.h>
#include <stdlib.h>
/* A linked list node */
struct Node {
int data;
struct Node* next;
};
/*Function to swap two integers at addresses a and b */
void swap(int* a, int* b);
/* Function to pairwise swap elements of a linked list */
void pairWiseSwap(struct Node* head)
{
struct Node* temp = head;
/* Traverse further only if there are at-least two nodes left */
while (temp != NULL && temp->next != NULL) {
/* Swap data of node with its next node's data */
swap(&temp->data, &temp->next->data);
/* Move temp by 2 for the next pair */
temp = temp->next->next;
}
}
/* UTILITY FUNCTIONS */
/* Function to swap two integers */
void swap(int* a, int* b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
/* Function to add a node at the beginning of Linked List */
void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* Function to print nodes in a given linked list */
void printList(struct Node* node)
{
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
}
/* Driver program to test above function */
int main()
{
struct Node* start = NULL;
/* The constructed linked list is:
1->2->3->4->5 */
push(&start, 50);
push(&start, 40);
push(&start, 30);
push(&start, 20);
push(&start, 10);
printf("Linked list before calling pairWiseSwap()\n");
printList(start);
pairWiseSwap(start);
printf("\nLinked list after calling pairWiseSwap()\n");
printList(start);
return 0;
}
#include <bits stdc++.h="">
using namespace std;
class node {
public:
int data;
node* next;
};
node* pairWiseSwap(node* head)
{
if (head == NULL || head->next == NULL)
return head;
node* prev = head;
node* curr = head->next;
head = curr;
while (true) {
node* temp = curr->next;
curr->next = prev;
if (temp == NULL || temp->next == NULL) {
prev->next = temp;
break;
}
prev->next = temp->next;
prev = temp;
curr = prev->next;
}
return head;
}
void push(node** head_ref, int new_data)
{
node* new_node = new node();
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
void print(node* node)
{
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
}
int main()
{
node* start = NULL;
push(&start, 5);
push(&start, 4);
push(&start, 3);
push(&start, 2);
push(&start, 1);
start = pairWiseSwap(start);
print(start);
return 0;
}
class PairWise
{
Node head;
class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
void pairWiseSwap()
{
Node temp = head;
/* Traverse only till there are atleast 2 nodes left */
while (temp != null && temp.next != null) {
/* Swap the data */
int k = temp.data;
temp.data = temp.next.data;
temp.next.data = k;
temp = temp.next.next;
}
}
public void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
void printList()
{
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
/* Driver program to test above functions */
public static void main(String args[])
{
PairWise llist = new PairWise();
llist.push(5);
llist.push(4);
llist.push(3);
llist.push(2);
llist.push(1);
System.out.println("Linked List before calling pairWiseSwap() ");
llist.printList();
llist.pairWiseSwap();
System.out.println("Linked List after calling pairWiseSwap() ");
llist.printList();
}
}
class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def pairwiseSwap(self): temp = self.head if temp is None: return while(temp and temp.next): if(temp.data != temp.next.data): temp.data, temp.next.data = temp.next.data, temp.data temp = temp.next.next def push(self, new_data): new_node = Node(new_data) new_node.next = self.head self.head = new_node def printList(self): temp = self.head while(temp): print(temp.data, end = " ") temp = temp.next llist = LinkedList() llist.push(5) llist.push(4) llist.push(3) llist.push(2) llist.push(1) llist.pairwiseSwap() llist.printList()
Output: 2 1 4 3 5
Space Complexity: O(1), constant space required as no extra space is used.
In this blog, we have discussed how to pairwise swap elements of a linked list by changing the links of the nodes directly in the most efficient way. This is one of the most popular interview problems and we have provided the full algorithm with all approaches, and code implementation in different languages with a dry run in picturised form.To practice, similar types of problems check out PrepBytes – MYCODE | Contest Footer
FAQs to pairwise swap elements of a linked list
- Can we swap on a linked list?
- Why stability in sorting is important?
- Why O(1) is fastest?
We can swap nodes of the linked list either by swapping their data or by changing the links (swapping nodes)
A stable sorting algorithm maintains the relative order of the items with equal sort keys.
O(1) is faster asymptotically as it is independent of the input