# Pairwise swap nodes of linked list

Examples:

```Example 1:
Input: Linked list: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL

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

Explanation: While traversing the linked list every time
we encounter a pair we have to swap them. i.e pair(1,2)
is swapped with (2,1), pair(3,4) is swapped with (4,3),
and so on.

Example 2:

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

Explanation: While traversing the linked list every time
we encounter a pair we have to swap them. Here the last
element 5 at the end of the list does not have any pair
to swap it with, so it remains unchanged.```

### Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution 1: Iterative method

Approach: Start the traversal from the head node of the linked list till the end of the linked list. While traversing swap data of each and every node with its next node’s data. until the appearance of null. i.e End of the list.

Let’s understand it with the help of some diagrams.

1st iteration: 2nd iteration: 3rd iteration: 4th iteration: Code:

## C++ Code

``````#include <bits/stdc++.h>

using namespace std;

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

/* Function to pairwise swap elements */

/* Traverse further only if
there are at-least two nodes left */
while (temp != NULL && temp -> next != NULL) {
/* Swap data of node with
its next node's data */
swap(temp -> data,
temp -> next -> data);

/* Move temp by 2 for the next pair */
temp = temp -> next -> next;
}
}

void push(Node ** head_ref, int new_data) {

Node * new_node = new Node();

new_node -> data = new_data;

new_node -> next = ( * head_ref);

}

void printList(Node * node) {
while (node != NULL) {
cout << node -> data << " ";
node = node -> next;
}
}

int main() {
Node * start = NULL;

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

cout << "Linked list " << "before calling pairWiseSwap()\n";
printList(start);

pairWiseSwap(start);

cout << "\nLinked list " <<
"after calling pairWiseSwap()\n";
printList(start);

return 0;
}``````

Output:

1 2 3 4 5
2 1 4 3 5

Time Complexity: O(n)

Reason: Linked list traversal takes linear time complexity

Space Complexity: O(1)

## Java Code

``````class TUF {

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

void pairWiseSwap() {

/* Traverse only till there are atleast 2 nodes left */
while (temp != null && temp.next != null) {

/* Swap the data */
int k = temp.data;
temp.data = temp.next.data;
temp.next.data = k;
temp = temp.next.next;
}
}

public void push(int new_data) {

Node new_node = new Node(new_data);
}

void printList() {
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}

public static void main(String args[]) {
TUF llist = new TUF();
llist.push(5);
llist.push(4);
llist.push(3);
llist.push(2);
llist.push(1);

System.out.println("Linked List before calling pairWiseSwap() ");
llist.printList();

llist.pairWiseSwap();

System.out.println("Linked List after calling pairWiseSwap() ");
llist.printList();
}
}``````

Output:

1 2 3 4 5
2 1 4 3 5

Time Complexity: O(n)

Reason: Linked list traversal takes linear time complexity

Space Complexity: O(1)

### Solution 2: Recursive method

Approach: If there are 2 or more than 2 nodes in Linked List then swap the first two nodes and recursively call for the rest of the list.

The base case will be the end of the list and the edge case will be the list with a size less than 2.

Code:

## C++ Code

``````#include <bits/stdc++.h>

using namespace std;

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

/* Function to pairwise swap elements */
/* There must be at-least two nodes in the list */

/* Swap the node's data with data of next node */

/* Call pairWiseSwap() for rest of the list */
}
}

void push(Node ** head_ref, int new_data) {

Node * new_node = new Node();
new_node -> data = new_data;
new_node -> next = ( * head_ref);
}

void printList(Node * node) {
while (node != NULL) {
cout << node -> data << " ";
node = node -> next;
}
}

int main() {
Node * start = NULL;

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

cout << "Linked list " << "before calling pairWiseSwap()\n";
printList(start);

pairWiseSwap(start);

cout << "\nLinked list " << "after calling pairWiseSwap()\n";
printList(start);

return 0;
}``````

Output:

1 2 3 4 5
2 1 4 3 5

Time Complexity: O(n)

Reason: Linked list traversal takes linear time complexity

Space Complexity: O(1)

## Java Code

``````class TUF {

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

/* There must be at-least two nodes in the list */

/* Swap the node's data with data of next node */

/* Call pairWiseSwap() for rest of the list */
}
}

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

void printList() {
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}

public static void main(String args[]) {
TUF llist = new TUF();
llist.push(5);
llist.push(4);
llist.push(3);
llist.push(2);
llist.push(1);

System.out.println("Linked List before calling pairWiseSwap() ");
llist.printList();

System.out.println("Linked List after calling pairWiseSwap() ");
llist.printList();
}
}``````

Output: