How to swap elements pair-wise in a linked list

A linked list is a data structure made of a chain of node objects. Each node contains a value and a pointer to the next node in the chain.

Note: To learn more about how a linked list can be implemented, refer to this link.

To swap all the elements of a linked list pair-wise, we can either swap the data values between each pair, or we can manipulate the pointers in the chain to move to the actual nodes of the pair themselves.

In this Answer, we'll explore how these approaches can be used to achieve this task and the circumstances in which one may be more useful than the other.

Swap nodes by swapping the data values

To swap elements pair-wise for the entire linked list, we need to go through the list until it has less than two nodes remaining. While doing so, we swap the current node's value with the node's value next to it. Since a pair has been swapped successfully, we need to move on to the next pair and swap it. To do this, we need to move two nodes along the list forward instead of 1.

Note: We only traverse the list as long as there are at least 2 nodes left in it because if it has 1 or 0 nodes left, then no pair-wise swapping can take place.

This approach is demonstrated below:

1 of 11

This approach takes O(N)O(N)time in the worst case, as it only involves traversing the linked list once. However, a problem arises when there are a lot of data fields in each node in the linked list. If we swap them individually, it can lead to many swap operations and slow the process. Hence, this approach should ideally be adopted when a node has few data fields.

Code

We can swap nodes pair-wise in a linked list by swapping their data values iteratively and recursively.

The highlighted lines in the C++ code below contain both the iterative and recursive implementations of the approach discussed above:

#include <iostream>
using namespace std;
class Node {
public:
int value;
Node* next;
Node()
{
next = NULL ;
}
Node(int val)
{
value = val ;
next = NULL ;
}
};
class LinkedList
{
public:
Node* head;
LinkedList(Node* to_make_head)
{
head = to_make_head ;
}
void iterativePairwiseSwap()
{
Node* current_node = head ;
while(1)
{
if(current_node == NULL || current_node->next == NULL) // if there are less than 2 nodes left in the linked list
{
return ;
}
// swapping the values of a node and its next node
int temp = current_node->value ;
current_node->value = current_node->next->value;
current_node->next->value = temp ;
current_node = current_node->next->next ;
}
}
void recursivePairwiseSwap(Node* head_of_current_list)
{
Node* current_node = head_of_current_list ;
if(current_node == NULL || current_node->next == NULL) // if there are less than 2 nodes left in the linked list
{
return ;
}
// swapping the values of a node and its next node
int temp = current_node->value ;
current_node->value = current_node->next->value ;
current_node->next->value = temp ;
recursivePairwiseSwap(current_node->next->next) ;
}
void push(int new_data)
{
Node* new_node = new Node();
new_node->value = new_data;
new_node->next = head;
head = new_node;
}
void printList()
{
Node* node = head;
while (node != NULL)
{
cout << node->value << " ";
node = node->next;
}
}
};
/* Driver program to test above function */
int main()
{
Node* head = new Node(7);
LinkedList example_list(head);
example_list.push(6);
example_list.push(5);
example_list.push(4);
example_list.push(3);
example_list.push(2);
example_list.push(1);
// The constructed linked list is:
// 1->2->3->4->5->6->7 */
cout << "Original linked list: ";
example_list.printList();
example_list.iterativePairwiseSwap();
cout << "\n\nLinked list after calling iterativePairwiseSwap(): ";
example_list.printList();
example_list.recursivePairwiseSwap(example_list.head);
cout << "\nLinked list after calling recursivePairwiseSwap(): ";
example_list.printList();
return 0;
}

Swap nodes by manipulating the pointers

To swap a pair of adjacent nodes x and y in a linked list such that x now lies ahead of y instead of y lying ahead of x, we need to change the link between x and y . This link is changed such that the next pointer of node x is not pointing to node y anymore, but is rather pointing to the element to the next node y. For this change, it doesn't matter where x and y occur in the list.

We must change the link between the node preceding the node x, and the node x. For this change, two different cases arise that depend on where x occurs in the list. If the node x is the head node, then we simply make the node y the head of the list. However, if x is not the head, then we need to update the next pointer of the node preceding x to point to y.

We must also change the link between the node y and the node proceeding y . This link is altered such that the next pointer of the node y no longer points to the node proceeding it but rather to the node x. For this change, it doesn't matter where x and y occur in the list.

If the nodes in the linked list contain a lot of data values, it is slow to swap each of them individually, as discussed in the first approach above. Hence, in this case, doing pair-wise swapping of nodes by swapping the actual nodes via the manipulation of their pointers is more efficient, even if both approaches take O(N)O(N) time (in the worst case) on paper.

Code

We can swap nodes pair-wise in a linked list by manipulating the pointers iteratively and recursively.

Note: The highlighted lines in the C++ code below contain both the iterative and recursive implementations of the approach discussed above.

#include <iostream>
using namespace std;
class Node {
public:
int value;
Node* next;
Node()
{
next = NULL ;
}
Node(int val)
{
value = val ;
next = NULL ;
}
};
class LinkedList
{
public:
Node* head;
LinkedList(Node* to_make_head)
{
head = to_make_head ;
}
// Iterative approach
void iterativePairwiseSwap()
{
Node* current_node = head ;
Node* previous_node = NULL;
// consider two nodes at a time and swap their links
while (1)
{
if(current_node == NULL || current_node->next == NULL) // less than 2 nodes left in the list
{
break ;
}
Node* temp = current_node->next; // second element (node) of the pair
current_node->next = temp->next; // for the first element in the pair: making its next pointer point to the node proceding its own next node (which is the second element of the pair)
temp->next = current_node; // for the second element in the pair: make its next pointer point to the first element of the pair
if (previous_node == NULL) // first pair in the list
{
head = temp;
}
else
{
previous_node->next = temp;
}
previous_node = current_node;
current_node = current_node->next;
}
}
// Recursive approach
void recursivePairwiseSwap(Node* current_head , Node* previous_node)
{
if (current_head == NULL || current_head->next == NULL) // less than 2 nodes left in the list
{
return;
}
else
{
// changing the pointers
Node* current_node = current_head; // first element (node) of the pair
Node* temp = current_node->next; // second element (node) of the pair
current_node->next = temp->next; // for the first element in the pair: making its next pointer point to the node proceding its own next node (which is the second element of the pair)
temp->next = current_node; // for the second element in the pair: make its next pointer point to the first element of the pair
if (previous_node == NULL) // first pair in the list
{
head = temp;
}
else
{
previous_node->next = temp;
}
recursivePairwiseSwap(current_node->next, current_node);
}
}
void push(int new_data)
{
Node* new_node = new Node();
new_node->value = new_data;
new_node->next = head;
head = new_node;
}
void printList()
{
Node* node = head;
while (node != NULL)
{
cout << node->value << " ";
node = node->next;
}
}
};
/* Driver program to test above function */
int main()
{
Node* head = new Node(7);
LinkedList example_list(head);
example_list.push(6);
example_list.push(5);
example_list.push(4);
example_list.push(3);
example_list.push(2);
example_list.push(1);
// The constructed linked list is:
// 1->2->3->4->5->6->7 */
cout << "Original linked list: ";
example_list.printList();
example_list.iterativePairwiseSwap();
cout << "\n\nLinked list after calling iterativePairwiseSwap(): ";
example_list.printList();
example_list.recursivePairwiseSwap(example_list.head , NULL);
cout << "\nLinked list after calling recursivePairwiseSwap(): ";
example_list.printList();
return 0;
}

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved