# Swap Nodes in Pairs Leetcode Solutions

Difficulty Level Medium
algorithms coding Interview interviewprep LeetCode LeetCodeSolutions Linked-ListViews 3679

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)

1. 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.
2. Now that we have a pair, use first and second to denote first and second items of our pair.
3. Since the first node would now become the tail of this pair,
1. call the recursive function starting from the next pair(node after second).
2. The subproblem is solved by the function and append it to first node.
3. Now, append the first node, which also has the rest of the list connected to it, to the second node.
4. Since we want the second node to be swapped with first, second will become head now,
1. Return second.

## Algorithm(Optimal)

1. Create a previous pointer pointing to some dummy node, maintain its prehead.
2. Set next of the previous node as the current head of the list.
3. This previous pointer can point to the next swapped pair.
4. If the list is NULL or has just one element
• return the list
5. 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)
6. The list still can be NULL or can have a single item left, so connect the prevNode to rest of the list.
7. 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;
}
};

{
{
cout << head->value << " ";
}
cout << '\n';
return;
}

{

second->next = first;
return second;
}

int main()
{

return 0;
}
```

#### Iterative Approach

```#include <bits/stdc++.h>
using namespace std;
struct listNode
{
int value;
listNode* next;
listNode(int x)
{
value = x;
next = NULL;
}
};

{
{
cout << head->value << " ";
}
cout << '\n';
return;
}

{

//initialise the prevNode
listNode *prevNode = new listNode(-1) , *prehead = prevNode;

listNode *first , *second , *temp;
//temporary variable to store first and second of every pair

{

temp = second->next;
second->next = first;
prevNode->next = second;
//connecting previous node to the second of this pair

prevNode = first;
//reinitialising previous node and head for next pair
}

}

int main()
{

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
{
{
{
}
return;
}

{

second.next = first;

return second;
}

public static void main(String args[])
{

}
}
```

#### Iterative Approach

```class listNode
{
int value;
listNode next;

listNode(int x)
{
value = x;
next = null;
}
}

class swap_nodes_in_pairs
{
{
{
}
return;
}

{

//initialise the prevNode
listNode prevNode = new listNode(-1) , prehead = prevNode;

listNode first , second , temp;
//temporary variable to store first and second of every pair

{

temp = second.next;
second.next = first;
prevNode.next = second;
//connecting previous node to the second of this pair

prevNode = first;
//reinitialising previous node and head for next pair
}

}

public static void main(String args[])
{

}
}
```
`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.

Translate »