# Swap Nodes In Pairs

Difficulty Level Medium
Frequently asked in Amazon Microsoft Moonfrog Labs

In swap nodes in pairs problem, we have given a linked list consisting of n nodes. Swap every node at even index with it’s a right adjacent node at odd index() considering index starting from 0.

## Example

Input : 1->2->3->4->NULL

Output : 2->1->4->3->NULL

Input : 1->2->3->4->5->6->7->NULL

Output : 2->1->4->3->6->5->7->NULL

## Iterative Method

### Algorithm

1. Create a class Node with an integer variable to store the data and a Pointer of type Node as it’s public members.
2. After that create a function to push the data inside the nodes and form a linked list.
3. Similarly, create the function to swap the nodes of the given linked list which accepts the head of the linked list as it’s a parameter.
4. Create a temporary Node type pointer and store the head in it.
5. Traverse while the temporary node pointer is not null and the next of the temporary node pointer is not null. Swap the data of the temporary node pointer with the data of the next of the temporary node pointer. Update the temporary node pointer as the next of the temporary node pointer.
6. Traverse again while the head is not equal to NULL. Print the data of the head and update the head as the next of the head.

Time Complexity: O(n)

Auxiliary Space: O(1)

### C++ Program to swap nodes in pairs

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

class Node{
public:
int data;
Node* next;
};

while((temp != NULL) && (temp->next != NULL)){
swap(temp->data, temp->next->data);

temp = temp->next->next;
}

}
cout<<"NULL";
}

Node* new_node = new Node();

new_node->data = new_data;

}

int main(){
Node* start = NULL;

push(&start, 7);
push(&start, 6);
push(&start, 5);
push(&start, 4);
push(&start, 3);
push(&start, 2);
push(&start, 1);

Swap(start);

return 0;
}```
`2->1->4->3->6->5->7->NULL`

### Java Program to swap nodes in pairs

```class List{

class Node{
int data;
Node next;
Node(int d){
data = d;
next = null;
}
}

void Swap(){

while((temp != null) && (temp.next != null)){

int k = temp.data;
temp.data = temp.next.data;
temp.next.data = k;
temp = temp.next.next;
}

}
System.out.print("NULL");
}

public void push(int new_data){
Node new_node = new Node(new_data);

}

public static void main(String args[]){
List l = new List();

l.push(7);
l.push(6);
l.push(5);
l.push(4);
l.push(3);
l.push(2);
l.push(1);

l.Swap();
}
}```
`2->1->4->3->6->5->7->NULL`

## Recursive Method

### Algorithm

1. Create a class Node with an integer variable to store the data and a Pointer of type Node as it’s public members.
2. After that create a function to push the data inside the nodes and form a linked list.
3. Similarly, create the function to swap the nodes of the given linked list which accepts the head of the linked list as it’s a parameter.
4. Create a temporary Node type pointer and store the head in it.
5. If the temporary Node type pointer is not equal to NULL and the next of the temporary Node type pointer is not equal to NULL, swap the data of the temporary node pointer with the data of the next of the temporary node pointer.
6. Update the temporary node pointer as the next of the next of the temporary node pointer. Make the recursive call to the function itself with the updated temporary node type pointer.
7. Traverse while the head is not equal to NULL. Print the data of the head and update the head as the next of the head.

Time Complexity: O(n)

Auxiliary Space: O(1)

### C++ Program to swap nodes in pairs

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

class Node{
public:
int data;
Node* next;
};

if((temp != NULL) && (temp->next != NULL)){
swap(temp->data, temp->next->data);

temp = temp->next->next;
Swap(temp);
}
}

}
cout<<"NULL";
}

Node* new_node = new Node();

new_node->data = new_data;

}

int main(){
Node* start = NULL;

push(&start, 7);
push(&start, 6);
push(&start, 5);
push(&start, 4);
push(&start, 3);
push(&start, 2);
push(&start, 1);

Swap(start);

print(start);

return 0;
}```
`2->1->4->3->6->5->7->NULL`

### Java Program to swap nodes in pairs

```class List{

class Node{
int data;
Node next;
Node(int d){
data = d;
next = null;
}
}

void Swap(){

if((temp != null) && (temp.next != null)){

int k = temp.data;
temp.data = temp.next.data;
temp.next.data = k;
temp = temp.next.next;
Swap();
}

while(start != null) {
System.out.print(start.data + "->");
start = start.next;
}
}

public void push(int new_data){
Node new_node = new Node(new_data);

}

public static void main(String args[]){
List l = new List();

l.push(7);
l.push(6);
l.push(5);
l.push(4);
l.push(3);
l.push(2);
l.push(1);

l.Swap();
System.out.print("NULL");
}
}```
`2->1->4->3->6->5->7->NULL`

References

Translate »