Swap nodes in a linked list without swapping data in C++
This article is about swapping nodes in a linked list without swapping data by changing links in the C++ language.
What is a Linked List?
A linked list is a linear data structure interconnected by nodes that are made up of two items – the data carried by the node and reference to the next node. Implementation of this dynamic data structure makes use of pointers.
About swapping nodes
Nodes containing two given keys namely p and q can be swapped by changing links which would require the help of two pointers one pointing at the current node and other at the previous node of the keys respectively.
Examples:-
Input: 1,2,3,4,5 , p=2 q=4
Output:1,4,3,2,5 , Here 2 is swapped with 4
Input:6,7,8,9,10 ,p=6 q=10
Output:10,7,8,9,6 , Here 6 is swapped with 10
Possible Cases:-
- p and/or q may not be present in the linked list.
- p or q may be the last node
- p and q may or may not be adjacent
- p or q may be the head node
The approach towards the question
p and q are two keys whose nodes are to be swapped. So basically what the idea is to make 2 pointers for both p and q of which one must point the current node and the other must point its previous node respectively. First, we will search the two keys whether they are present or not. If not present, then return. If present then we will change links between those two nodes with the use of current and previous pointers. Let us see how it’s done with the help of the code below.
C++ Program to swap nodes in a linked list without swapping data
#include<bits/stdc++.h> using namespace std; //creation of linked list struct node { int value; node *next; }; //function to create add that node in the linked list void create_node(node **head,int a) { node* new_node=new node(); new_node->value=a; new_node->next=*head; *head=new_node; } //function to print the linked list void print(node *trav) { while(trav!=NULL) { cout<<trav->value<<" "; trav=trav->next; } } //function to swap two nodes void swap_nodes(node **head,int p,int q) { if(p==q) return; //if p and q are same, break node *p_prev=NULL,*p_curr=*head,*q_prev=NULL,*q_curr=*head; //searching p and moving pointer to it while(p_curr!=NULL&&p_curr->value!=p) { p_prev=p_curr; p_curr=p_curr->next; } //searching q and moving pointer to it while(q_curr!=NULL&&q_curr->value!=q) { q_prev=q_curr; q_curr=q_curr->next; } //if either not present, break if(p_curr==NULL || q_curr==NULL) return; //check if p is head of the list if(p_prev!=NULL) p_prev->next=q_curr; else *head=q_curr; //check if q is head of the list if(q_prev!=NULL) q_prev->next=p_curr; else *head=p_curr; //swapping remaining pointers accordingly node* pole=q_curr->next; q_curr->next=p_curr->next; p_curr->next=pole; } int main() { struct node *start=NULL; int a[]={5,4,3,2,1}; for(int i=0;i<5;i++) { create_node(&start,a[i]); } cout<<"Before swapping:"; print(start); cout<<endl; swap_nodes(&start,2,5); cout<<"After swapping:"; print(start); }
Output:
Before swapping:1 2 3 4 5 After swapping: 1 5 3 4 2
Since the two nodes to be swapped were 2 and 5, the output is 1 5 3 4 2.
Thank you for reading!!
I hope it helps!!
Leave a Reply