## We are given a linked list and two key values, we need to swap these nodes.

### Example

**Time complexity : O(n)**

## Algorithm

**We need to handle these cases,**

**a.** x and/or y may not present in the linked list.

**b.** x or y may be last node.

**c.** x or y may be head node.

**d.** x and y may or may not be adjacent.

**In the swap function,**

**1.** If x and y are same, do nothing just return the same linked list.

**2.** Search for x and y, if either of x or y is not present, do nothing just return the same linked list.

**3.** If x is not head, make x_prev->next as y, else make y as new head.

**4.** If y is not head, make y_prev->next as x, else make x as new head.

**5.** Swap next pointers. (x->next, y->next)

## C++ Program

```
#include <bits/stdc++.h>
using namespace std;
struct LLNode
{
int data;
struct LLNode* next;
};
/* Function to insertAtBeginning a node */
void insertAtBeginning(struct LLNode** head, int dataToBeInserted)
{
struct LLNode* curr = new LLNode;
curr->data = dataToBeInserted;
curr->next = NULL;
if(*head == NULL)
*head=curr; //If this is first node make this as head of list
else
{
curr->next=*head; //else make the curr (new) node's next point to head and make this new node a the head
*head=curr;
}
//O(1) constant time
}
//display linked list
void display(struct LLNode**node)
{
struct LLNode *temp= *node;
while(temp!=NULL)
{
if(temp->next!=NULL)
cout<<temp->data<<"->";
else
cout<<temp->data;
temp=temp->next; //move to next node
}
//O(number of nodes)
cout<<endl;
}
/* Function to swap nodes x and y in linked list by
changing links */
void swapNodes(struct LLNode **head_ref, int x, int y)
{
//If x and y are same
if (x == y)
{
return;
}
//search for x and store previous of x
struct LLNode *x_prev = NULL, *x_curr = *head_ref;
while (x_curr && x_curr->data != x)
{
x_prev = x_curr;
x_curr = x_curr->next;
}
//search for y and store previous of y
struct LLNode *y_prev = NULL, *y_curr = *head_ref;
while (y_curr && y_curr->data != y)
{
y_prev = y_curr;
y_curr = y_curr->next;
}
//x or y not present
if (x_curr == NULL || y_curr == NULL)
{
return;
}
//If x is not head
if (x_prev != NULL)
{
x_prev->next = y_curr;
}
//If x is head
//make y as new head
else
{
*head_ref = y_curr;
}
//If y is not head
if (y_prev != NULL)
y_prev->next = x_curr;
//If y is head
//make x as new head
else
{
*head_ref = x_curr;
}
// Swap next pointers
struct LLNode *temp = y_curr->next;
y_curr->next = x_curr->next;
x_curr->next = temp;
}
//Main function
int main()
{
struct LLNode* head = NULL;//Initial list has no elements
insertAtBeginning(&head, 9);
insertAtBeginning(&head, 8);
insertAtBeginning(&head, 7);
insertAtBeginning(&head, 6);
insertAtBeginning(&head, 5);
insertAtBeginning(&head, 4);
insertAtBeginning(&head, 3);
insertAtBeginning(&head, 2);
insertAtBeginning(&head, 1);
cout<<"Input linked list is: ";
display(&head);
int x = 2, y = 7;
swapNodes(&head,x,y);
cout<<"output LL after swapping "<<x<<" and "<<y<<" is: ";
display(&head);
return 0;
}
```

Try It

**Next >**
**< Prev**