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.
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:
This approach takes
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 nodeint 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 nodeint 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;}
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
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 approachvoid iterativePairwiseSwap(){Node* current_node = head ;Node* previous_node = NULL;// consider two nodes at a time and swap their linkswhile (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 paircurrent_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 pairif (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 approachvoid 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 pointersNode* current_node = current_head; // first element (node) of the pairNode* temp = current_node->next; // second element (node) of the paircurrent_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 pairif (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