**Difficulty:** Medium, **Asked-in:** Facebook, Microsoft, Amazon, Adobe, Yahoo.

**Key takeaway:** An excellent problem to learn problem-solving using iteration and recursion in a linked list.

Given a singly linked list, write a program to swap every two adjacent nodes and return its head. If the number of nodes is odd, then we need to pair-wise swap all the elements except the last element.

**Input:** 12->42->9->30->56->20->NULL

**Output:** 42->12->30->9->20->56->NULL

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

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

- Iterative approach by changing the node pointers
- Recursive approach by changing the node pointers
- Iterative approach by swapping node values
- Recursive approach by swapping node values

The idea is to traverse the linked list linearly, pick the nodes in pairs, and swap their links. By the end of the process, we return the head pointer of the modified list. The idea looks simple, but we need to be careful with the pointer's movement.

We define a function **pairWiseSwap(ListNode head)**, which takes the head of the linked list as input and returns the head pointer of the pair-wise swapped linked list.

**Step 1:** If the linked list is empty or there is a single node, we return the head as an output, i.e., **if (head == NULL || head->next == NULL)**, **return head**. Otherwise, we move forward in a loop to pick nodes in pairs and swap their links.

**Step 2:** Before starting the loop:

- We define the head of the modified linked list, which will be the second node from the start i.e.
**newHead = head->next.** - We initialize a loop pointer
**currNode**with the head node to track the pair of nodes i.e. current and next node in the linked list.

**Step 3:** Now we run a loop to swap list nodes in pairs by changing links. What will be the loop condition? The idea is simple: We are considering two nodes simultaneously, so we run the loop till **currNode** and **currNode->next** are not NULL. Now we perform the pointers swapping inside the while loop.

- We create a temporary pointer,
**temp**, and assign it to**currNode->next**. This will help us to store the next node temporarily. - We then update
**currNode->next**to skip the next node and directly point to the node after it (**currNode->next = currNode->next->next**). This will effectively remove the next node from its current position. - Now we swap the positions of
**currNode**and**temp**by setting**temp->next**to**currNode.** - We move the
**currNode**pointer to the next position (**currNode = currNode->next**) to continue traversing the linked list. - If
**currNode**and its adjacent node are both not NULL, we update the**temp->next->next**pointer to point to the next node after**currNode**. This step will ensure that the swapped nodes are correctly linked to the rest of the list.

**Step 4:** After the completion of the while loop, we have completed the pairwise swapping, and the newHead pointer points to the correct head of the modified linked list. So we return newHead.

The overall idea is to use two pointers (currNode and temp) to perform the pairwise swapping and update the necessary pointers at each step to ensure the correct connections between nodes.

```
ListNode* pairWiseSwap(ListNode* head)
{
if (head == NULL || head->next == NULL)
return head;
ListNode* currNode = head;
ListNode* newHead = head->next;
while (currNode != NULL && currNode->next != NULL)
{
ListNode* temp = currNode->next;
currNode->next = currNode->next->next;
temp->next = currNode;
currNode = currNode->next;
if (currNode != NULL && currNode->next != NULL)
temp->next->next = currNode->next;
}
return newHead;
}
```

```
def pairWiseSwap(head):
if head is None or head.next is None:
return head
currNode = head
newHead = head.next
while currNode is not None and currNode.next is not None:
temp = currNode.next
currNode.next = currNode.next.next
temp.next = currNode
currNode = currNode.next
if currNode is not None and currNode.next is not None:
temp.next.next = currNode.next
return newHead
```

```
class PairwiseSwapLinkedList
{
public static ListNode pairWiseSwap(ListNode head)
{
if (head == null || head.next == null)
return head;
ListNode currNode = head;
ListNode newHead = head.next;
while (currNode != null && currNode.next != null)
{
ListNode temp = currNode.next;
currNode.next = currNode.next.next;
temp.next = currNode;
currNode = currNode.next;
if (currNode != null && currNode.next != null)
temp.next.next = currNode.next;
}
return newHead;
}
}
```

We are doing a single traversal of the linked list and performing pointer movement operations at each iteration. In other words, we are doing constant operations with each node in the linked list. So, **time complexity = O(n)**, where n is the number of nodes. We are using constant extra space, so **space complexity = O(1).**

Now a critical question is: Can we solve this problem using the solution of a smaller sub-problem i.e. using recursion? If yes, then what would be the recursive structure? Let's think!

Suppose there are n nodes in the linked list, and we swap the first two nodes. Now the problem will get reduced to swapping the remaining n - 2 nodes in pairs. So the solution idea would be to swap the first two nodes and call the same function for the remaining list if there are more than two nodes in the list. By the end of the process, we should return the head of the modified linked list.

**Recursive structure:** Pair-wise swapping of linked list size of n = Swapping the first two nodes + Pair-wise swapping of the remaining linked list of size n - 2 recursively.

- Base case: This is a situation when there is a single node or no node in the linked list.
**if (head == NULL || head->next == NULL), return head.** -
Now, we swap the first pair of nodes i.e. head and head->next.

- We first save the head of the remaining list in a pointer variable for the input parameter of the recursive call i.e.
**remainingListHead = head->next->next.** - We update the new head pointer of the modified linked list, which would be the head->next.
**newHead = head->next.** - Finally, we update the newHead next pointer with the head node.
**newHead->next = head**

- We first save the head of the remaining list in a pointer variable for the input parameter of the recursive call i.e.
- After swapping the first two nodes, we call the same function to swap the remaining linked list with remaingListHead as the input parameter. This function returns the head of the remaining modified linked list, which would be the next pointer of the head node.
**head->next = pairWiseSwap(remainingListHead).**Think! - Finally, we return
**newHead**as an output.

```
ListNode* pairWiseSwap(ListNode* head)
{
if (head == NULL || head->next == NULL)
return head;
ListNode* remainingListHead = head->next->next;
ListNode* newHead = head->next;
newHead->next = head;
head->next = pairWiseSwap(remainingListHead);
return newHead;
}
```

```
def pairWiseSwap(head):
if head is None or head.next is None:
return head
remainingListHead = head.next.next
newHead = head.next
newHead.next = head
head.next = pairWiseSwap(remainingListHead)
return newHead
```

```
public class PairwiseSwapLinkedList
{
public static ListNode pairWiseSwap(ListNode head)
{
if (head == null || head.next == null)
return head;
ListNode remainingListHead = head.next.next;
ListNode newHead = head.next;
newHead.next = head;
head.next = pairWiseSwap(remainingListHead);
return newHead;
}
}
```

Suppose the total number of nodes in the linked list is n.

- At each step of recursion, we are swapping one pair of nodes. In other words, our input size will decrease by 2 at each step of recursion.
- We are performing O(1) or constant operations at each step of recursion.
- So time complexity function T(n) = T(n-2) + O(1), where the base case is the situation of T(1) = c and T(0) = c.
- The basic analysis of the above recurrence is very simple: Recursion will terminate at base case after n/2 number of steps. Why? Because at each step, the input size is decreasing by 2! So
**time complexity = n/2*O(1) = O(n).**Explore this blog to understand the concept of recursion analysis: Analysis of Recursion.

The space complexity depends on the size of the recursion call stack which will be equal to the height of the recursion tree. There would be a total n/2 number of recursive calls till our recursion reach the base case, so the height of the recursion tree = n/2. For this, recursion will use a call stack of size n/2, so **space complexity = O(n).** Think!

We can solve this problem using another idea: Swapping node values in pairs instead of changing pointers. The solution begins with the first node and keeps swapping values in pairs till we reach the NULL node. Here we swap the data of the nodes keeping their addresses as it is.

**Efficiency note:** If data contains too many fields, then we need to perform several swap operations. So swapping links is an efficient idea in comparison to swapping values! Think!

- Create a temporary variable and assign it to the head node i.e.
**temp = head.** - Now we run a loop till
**temp != NULL && temp->next != NULL**. - At each step of iteration, we swap the value of one pair of nodes and move to
**temp->next->next.** - By the end of the loop, we return the head pointer.

```
ListNode* pairWiseSwap(ListNode* head)
{
if (head == NULL || head->next == NULL)
return head;
ListNode* temp = head;
while (temp != NULL && temp->next != NULL)
{
swap(temp->val, temp->next->val);
temp = temp->next->next;
}
return head;
}
```

```
def pairWiseSwap(head):
if head is None or head.next is None:
return head
temp = head
while temp is not None and temp.next is not None:
temp.val, temp.next.val = temp.next.val, temp.val
temp = temp.next.next
return head
```

```
public class PairwiseSwapLinkedList
{
public static ListNode pairWiseSwap(ListNode head)
{
if (head == null || head.next == null)
return head;
ListNode temp = head;
while (temp != null && temp.next != null)
{
int tempVal = temp.val;
temp.val = temp.next.val;
temp.next.val = tempVal;
temp = temp.next.next;
}
return head;
}
}
```

We are doing a single traversal of the linked list and performing data swapping operations at each iteration. Suppose we have m data fields in a linked list node, then we need to swap each data field for each pair of nodes. In other words, we need to perform O(m) data swapping operations for each node during the swapping operation.

If the total number of nodes is n, time complexity = Time complexity of data swapping for each pair of nodes * total number of node pairs = O(m) * n/2 = O(mn).

- If m is constant then time complexity = O(n).
- If m ~ n, then time complexity = O(n^2).

We are using constant extra space, so space complexity = O(1).

We can also think to implement the above approach recursively. If there are 2 or more than 2 nodes in the linked list then we swap the first two nodes and recursively swap pair-wise nodes for the remaining linked list.

**Recursive structure:** pairWiseSwap(head) = swap(head->data, head->next->data) + pairWiseSwap(head->next->next)

**Base case:** if (head == NULL || head->next == NULL), return head.

```
ListNode* pairWiseSwap(ListNode* head)
{
if (head == NULL || head->next == NULL)
return head;
else
{
swap(head->val, head->next->val);
pairWiseSwap(head->next->next);
return head;
}
}
```

```
def pairWiseSwap(head):
if head is None or head.next is None:
return head
head.val, head.next.val = head.next.val, head.val
pairWiseSwap(head.next.next)
return head
```

```
public class PairwiseSwapLinkedList
{
public static ListNode pairWiseSwap(ListNode head)
{
if (head == null || head.next == null)
return head;
else
{
int tempVal = head.val;
head.val = head.next.val;
head.next.val = tempVal;
pairWiseSwap(head.next.next);
return head;
}
}
}
```

Suppose the total number of nodes in the linked list is n.

- Here at each step of recursion, we are swapping data of one pair of nodes. In other words, our input size will decrease by 2 at each step of recursion.
- Suppose there are m data fields in a linked list node, so we need to perform O(m) data swapping operations at each step of recursion.
- Time complexity function T(n) = T(n-2) + O(m), where base case is the situation of T(1) = c and T(0) = c.
- The basic analysis of the above recurrence is very simple: Recursion will terminate at base case after n/2 number of steps. Why? because at each step, the input size is decreasing by 2! So
**time complexity = n/2*O(m) = O(nm).** - If m is constant then the time complexity = O(n)
**,**If m ~ n, then time complexity = O(n^2).

The space complexity depends on the size of the recursion call stack which will be equal to the height of the recursion tree. There would be a total n/2 number of recursive calls till our recursion reach the base case. For this, the size of the call stack would be O(n), so **space complexity = O(n).**

- What would be the solution approach if a doubly-linked list is given instead of a singly-linked list?
- A dummy node is often used in linked list questions to avoid a special case at the beginning of the list. How can we apply the dummy node idea to this problem?
- How can we use the double-pointer (pointer to pointer) to solve this problem, so we do not need to update the head pointer separately during the swap?
- This problem is a special case of "reverse every k nodes of a linked list" with k = 2. Think about it!
- How can we modify the above iterative solutions to solve this problem using two pointers: "prev" and "curr"?
- Can we think of solving the recursive solution by recursively performing pair-wise swapping of the remaining list of size n-2 and then swapping the links of the first two nodes?
- Why is the solution involving swapping links better compared to swapping data?

- Remove nth node from list end
- The intersection of two sorted linked lists
- Find the middle node of a linked list
- Reversing a linked list
- Detect loop in a linked list
- Reverse nodes in k-group
- Swap Kth node from beginning with Kth node from the end in a linked list
- Reverse even elements in a linked list
- Move last m elements to the front of a given linked list
- Check if elements of the linked list are present in pair

If you have any queries or feedback, please write us at contact@enjoyalgorithms.com.**Enjoy learning, Enjoy coding, Enjoy algorithms!**

Subscribe to get well designed content on data structure and algorithms, machine learning, system design, object orientd programming and math.

©2023 Code Algorithms Pvt. Ltd.

All rights reserved.