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.
Table of Contents
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
- Create a class Node with an integer variable to store the data and a Pointer of type Node as it’s public members.
- After that create a function to push the data inside the nodes and form a linked list.
- 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.
- Create a temporary Node type pointer and store the head in it.
- 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.
- 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;
};
void Swap(Node* head){
Node* temp = head;
while((temp != NULL) && (temp->next != NULL)){
swap(temp->data, temp->next->data);
temp = temp->next->next;
}
while (head != NULL) {
cout<<head->data<<"->";
head = head->next;
}
cout<<"NULL";
}
void push(Node** head_ref, int new_data){
Node* new_node = new Node();
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
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{
Node head;
class Node{
int data;
Node next;
Node(int d){
data = d;
next = null;
}
}
void Swap(){
Node temp = head;
while((temp != null) && (temp.next != null)){
int k = temp.data;
temp.data = temp.next.data;
temp.next.data = k;
temp = temp.next.next;
}
while(head != null) {
System.out.print(head.data + "->");
head = head.next;
}
System.out.print("NULL");
}
public void push(int new_data){
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
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
- Create a class Node with an integer variable to store the data and a Pointer of type Node as it’s public members.
- After that create a function to push the data inside the nodes and form a linked list.
- 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.
- Create a temporary Node type pointer and store the head in it.
- 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.
- 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.
- 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;
};
void Swap(Node* head){
Node* temp = head;
if((temp != NULL) && (temp->next != NULL)){
swap(temp->data, temp->next->data);
temp = temp->next->next;
Swap(temp);
}
}
void print(Node* head){
while(head != NULL) {
cout<<head->data<<"->";
head = head->next;
}
cout<<"NULL";
}
void push(Node** head_ref, int new_data){
Node* new_node = new Node();
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
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{
Node head,start;
class Node{
int data;
Node next;
Node(int d){
data = d;
next = null;
}
}
void Swap(){
Node temp = head;
if((temp != null) && (temp.next != null)){
int k = temp.data;
temp.data = temp.next.data;
temp.next.data = k;
temp = temp.next.next;
head = temp;
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);
new_node.next = head;
head = new_node;
start = head;
}
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