# Pairwise swap elements of a given linked list by chnaging links

## Given a singly linked list, write a function to swap elements pairwise. In the below methods the main idea is to swap links rather than swapping the data.

### Example

INPUT :
23 ->1 ->50 ->15 ->16 ->6

OUTPUT :
1 ->23 ->15 ->50 ->6 ->16

In the above example we can see that the elements are swaped pairwise ie, (1,23), (50,15) and (16,6)

### Method 1 :

Time Complexity : O(n)

## Algorithm

Till the end of the list

1. Initialize "next" pointer to "curr's" next and change next of "curr" as previous node
ie,  changing the direction of the link

2. Change next of "prev" to "next" next ie, skipping two nodes

3. Update "prev" and "curr" to "next" and "prev" next respectively

The above Algorithm can be clearly explained in below diagram

## C++ Program

``````#include <bits/stdc++.h>
using namespace std;

struct LLNode{
int data;
LLNode *next;
};
//This funnction will swap the elements pairwise
{
// If linked list is empty or there is only one node in list
return;

// Initialize previous and current pointers

// Traverse the list
while (true)
{
LLNode *next = curr->next;
curr->next = prev; // Change next of current as previous node

// If next NULL or next is the last node
if (next == NULL || next->next == NULL)
{
prev->next = next;
break;
}

// Change next of previous to next next
prev->next = next->next;

// Update previous and curr
prev = next;
curr = prev->next;
}
}
{
LLNode*curr=new LLNode;
//make a new node with this data and next pointing to NULL
curr->data=dataToBeInserted;
curr->next=NULL;

if(*head==NULL) //if list is empty then set the current formed node as head of list

else //make the next of the current node point to the present head and make the current node as the new head
{
}

//O(1) constant time
}

{
while(temp!=NULL) //till the list ends (NULL marks ending of list)
{
if(temp->next!=NULL)
cout<<temp->data<<" ->";
else
cout<<temp->data;

temp=temp->next; //move to next node
}
//O(number of nodes)
cout<<endl;
}

int main()
{

LLNode *head = NULL; //initial list has no elements

cout<<"\nCurrent List is :-\n";
cout<<"After doing PairWise Swap"<<endl;
return 0;
}``````

### Method 2

Recursive Implementation

## Algorithm

Change the links for first two nodes

1. Store the head of the list after two nodes ie, temp = head->next->next

Make the recursive call to the rest of the list

## C++ Program

``````#include <bits/stdc++.h>
using namespace std;

struct LLNode{
int data;
LLNode *next;
};
//This funnction will swap the elements pairwise
{
// If the list is empty or has only one node

// Store head of list after two nodes

// Change next of second node

// Recur for remaining list and change next of head

// Return new head of modified list
}
{
LLNode*curr=new LLNode;
//make a new node with this data and next pointing to NULL
curr->data=dataToBeInserted;
curr->next=NULL;

if(*head==NULL) //if list is empty then set the current formed node as head of list

else //make the next of the current node point to the present head and make the current node as the new head
{
}

//O(1) constant time
}

{
while(temp!=NULL) //till the list ends (NULL marks ending of list)
{
if(temp->next!=NULL)
cout<<temp->data<<" ->";
else
cout<<temp->data;

temp=temp->next; //move to next node
}
//O(number of nodes)
cout<<endl;
}

int main()
{

LLNode *head = NULL; //initial list has no elements
LLNode *result = NULL;

cout<<"\nCurrent List is :-\n";