C++ - Swap node values of a Circular Singly Linked List
There are many instances where it is required to swap value of two nodes while working with a list. This can be achieved by traversing to the interested nodes and swap their values if the nodes are valid. For example - if the given list is 10->20->30->40->50. After swapping values of first and fourth nodes, the list will become 40->20->30->10->50.
The function swapNodeValues is created for this purpose which is a 4-step process.
void swapNodeValues(int node1, int node2) { //1. count the number of nodes in the list Node* temp = head; int N = 0; if(temp != NULL) { N++; temp = temp->next; } while(temp != head) { N++; temp = temp->next; } //2. check if the swap positions are valid entries if(node1 < 1 || node1 > N || node2 < 1 || node2 > N) return; //3. traverse to the nodes where values to be swapped Node* pos1 = head; Node* pos2 = head; for(int i = 1; i < node1; i++) { pos1 = pos1->next; } for(int i = 1; i < node2; i++) { pos2 = pos2->next; } //4. swap the values of two nodes int val = pos1->data; pos1->data = pos2->data; pos2->data = val; }
The below is a complete program that uses above discussed concept to swap values of two given nodes of a circular singly linked list.
#include <iostream> using namespace std; //node structure struct Node { int data; Node* next; }; class LinkedList { private: Node* head; public: LinkedList(){ head = NULL; } //Add new element at the end of the list void push_back(int newElement) { Node* newNode = new Node(); newNode->data = newElement; newNode->next = NULL; if(head == NULL) { head = newNode; newNode->next = head; } else { Node* temp = head; while(temp->next != head) temp = temp->next; temp->next = newNode; newNode->next = head; } } //swap node values void swapNodeValues(int node1, int node2) { Node* temp = head; int N = 0; if(temp != NULL) { N++; temp = temp->next; } while(temp != head) { N++; temp = temp->next; } if(node1 < 1 || node1 > N || node2 < 1 || node2 > N) return; Node* pos1 = head; Node* pos2 = head; for(int i = 1; i < node1; i++) { pos1 = pos1->next; } for(int i = 1; i < node2; i++) { pos2 = pos2->next; } int val = pos1->data; pos1->data = pos2->data; pos2->data = val; } //display the content of the list void PrintList() { Node* temp = head; if(temp != NULL) { cout<<"The list contains: "; while(true) { cout<<temp->data<<" "; temp = temp->next; if(temp == head) break; } cout<<endl; } else { cout<<"The list is empty.\n"; } } }; // test the code int main() { LinkedList MyList; //Add five elements in the list. MyList.push_back(10); MyList.push_back(20); MyList.push_back(30); MyList.push_back(40); MyList.push_back(50); //Display the content of the list. MyList.PrintList(); //swap values of node=1 and node=4 MyList.swapNodeValues(1, 4); //Display the content of the list. MyList.PrintList(); return 0; }
The above code will give the following output:
The list contains: 10 20 30 40 50 The list contains: 40 20 30 10 50