# Swap nodes in a linked list without swapping data in C++

### 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;
}

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

//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;

//check if q is head of the list
if(q_prev!=NULL) q_prev->next=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!!