The goal of this problem is to swap nodes of a given linked list in pairs, that is, swapping every two adjacent nodes. If we are allowed to swap just the value of the list nodes, the problem would be trivial. So, we are not allowed to modify the node values.

## Example

1 2 3 4

2 1 4 3

6 7 3

7 6 3

## Approach

We can notice that we can swap the two nodes in a pair. The swap here means to manipulate the pointers so that the first node is connected to the remaining of the linked list and the second node now becomes **head **pointing to the first node.

The remaining list after this swap now becomes a sub-problem of what out initial problem was. So, we can call the same recursive function to the rest of the list. Here, we must keep track that the **headĀ **of the list is now actually the second node in the list. This is a sufficient solution but consumes space because recursion creates stack frames in the memory.

The Optimal method can be easily thought as a similar approach implemented iteratively. For this purpose, we need to create a * previous* node that will store the tail of just previous pair we swapped. After swapping the nodes of the current pair, we connect the tail of the previous pair to head of this pair.

## Algorithm(Recursive Approach)

- Simple base conditions are when do not even have two nodes to form a pair. In that case:
- The list can be
**NULL**or can comprise one item. - Return it as it.

- The list can be
- Now that we have a pair, use
**first**and**second**to denote first and second items of our pair. - Since the
**firstĀ**node would now become the tail of this pair,- call the recursive function starting from the next pair(node after
**second**). - The subproblem is solved by the function and append it to
**first**node. - Now, append the
**first**node, which also has the**rest**of the list connected to it, to the second node.

- call the recursive function starting from the next pair(node after
- Since we want the
**second**node to be swapped with**first, second**will become head now,- Return
**second.**

- Return

## Algorithm(Optimal)

- Create a
**previous**pointer pointing to some dummy node, maintain its**prehead**. - Set
**next**of the previous node as the current head of the list. - This previous pointer can point to the next swapped pair.
- If the list is
**NULL**or has just one element- return the list

- Keep iterating till we reach a point where the list terminates or has just one node left:
- Store the address of next pair in a
**temp**variable. - Swap the two nodes in this pair: first node and the second node
- Connect the prevNode to the second node of this pair
- Update the prevNode as the first node(as it will become the tail now)
- Update head = temp so that we can
**jump**to next pair

- Store the address of next pair in a
- The list still can be
**NULL**or can have a single item left, so connect the prevNode to rest of the list. - return dummy.next to get the required list.

## Implementation

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

#### Recursive Approach

#include <bits/stdc++.h> using namespace std; struct listNode { int value; listNode* next; listNode(int x) { value = x; next = NULL; } }; void print(listNode* head) { while(head) { cout << head->value << " "; head = head->next; } cout << '\n'; return; } listNode* swapNodesInPairs(listNode* head) { if(head == NULL || head->next == NULL) return head; listNode* first = head , *second = head->next; first->next = swapNodesInPairs(head->next->next); second->next = first; return second; } int main() { listNode* head = new listNode(1); head->next = new listNode(2); head->next->next = new listNode(3); print(swapNodesInPairs(head)); return 0; }

#### Iterative Approach

#include <bits/stdc++.h> using namespace std; struct listNode { int value; listNode* next; listNode(int x) { value = x; next = NULL; } }; void print(listNode* head) { while(head) { cout << head->value << " "; head = head->next; } cout << '\n'; return; } listNode* swapNodesInPairs(listNode* head) { if(head == NULL || head->next == NULL) return head; //initialise the prevNode listNode *prevNode = new listNode(-1) , *prehead = prevNode; prevNode->next = head; listNode *first , *second , *temp; //temporary variable to store first and second of every pair while(head != NULL && head->next != NULL) { first = head; second = head->next; temp = second->next; second->next = first; prevNode->next = second; //connecting previous node to the second of this pair prevNode = first; head = temp; //reinitialising previous node and head for next pair } prevNode->next = head; return prehead->next; } int main() { listNode* head = new listNode(1); head->next = new listNode(2); head->next->next = new listNode(3); print(swapNodesInPairs(head)); return 0; }

2 1 3

### Java Program to swap nodes in pairs leetcode solutions

#### Recursive Approach

class listNode { int value; listNode next; listNode(int x) { value = x; next = null; } } class swap_nodes_in_pairs { public static void print(listNode head) { while(head != null) { System.out.print(head.value + " "); head = head.next; } return; } public static listNode swapNodesInPairs(listNode head) { if(head == null || head.next == null) return head; listNode first = head , second = head.next; first.next = swapNodesInPairs(head.next.next); second.next = first; return second; } public static void main(String args[]) { listNode head = new listNode(1); head.next = new listNode(2); head.next.next = new listNode(3); head.next.next.next = new listNode(4); print(swapNodesInPairs(head)); } }

#### Iterative Approach

class listNode { int value; listNode next; listNode(int x) { value = x; next = null; } } class swap_nodes_in_pairs { public static void print(listNode head) { while(head != null) { System.out.print(head.value + " "); head = head.next; } return; } public static listNode swapNodesInPairs(listNode head) { if(head == null || head.next == null) return head; //initialise the prevNode listNode prevNode = new listNode(-1) , prehead = prevNode; prevNode.next = head; listNode first , second , temp; //temporary variable to store first and second of every pair while(head != null && head.next != null) { first = head; second = head.next; temp = second.next; second.next = first; prevNode.next = second; //connecting previous node to the second of this pair prevNode = first; head = temp; //reinitialising previous node and head for next pair } prevNode.next = head; return prehead.next; } public static void main(String args[]) { listNode head = new listNode(1); head.next = new listNode(2); head.next.next = new listNode(3); head.next.next.next = new listNode(4); print(swapNodesInPairs(head)); } }

2 1 4 3

## Complexity Analysis

### Time Complexity to swap nodes in pairs

*Recursive Approach*: **O(N)**, as we only do a single pass on the list. *Iterative Approach*: **O(N)**, again we do a single pass.

### Space Complexity to swap nodes in pairs

*Recursive Approach*: **O(N)**, as the recursion creates stack frames for every call in the memory. *Iterative Approach*: **O(1), **as constant space is used for some variables. This is where the iterative approach is **better**.