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!!