Swap Nodes in Pairs

Swap Nodes in Pairs

What is this problem about?

The Swap Nodes in Pairs coding problem is a fundamental linked list manipulation task. Given a linked list, you need to swap every two adjacent nodes and return its head. For example, if the input is 1 -> 2 -> 3 -> 4, the output should be 2 -> 1 -> 4 -> 3. You must solve this by actually swapping the nodes themselves, not just the values within the nodes.

Why is this asked in interviews?

This is a quintessential linked list question asked by companies like Amazon, Microsoft, and Adobe. It tests your ability to manipulate pointers without losing track of the list's structure. It evaluates your precision—getting the order of pointer assignments wrong can easily lead to lost nodes or infinite loops. It also provides a great opportunity to demonstrate both iterative and recursive problem-solving skills.

Algorithmic pattern used

The primary patterns are Linked List manipulation and Recursion.

• Recursive: Swap the first two nodes, then recursively call the function for the rest of the list and attach the result to the end of the newly swapped pair.
• Iterative: Use a "dummy" node to handle the head swap gracefully. Iterate through the list with a pointer, swapping the next two nodes by reassigning their next pointers and updating the previous node's next to point to the new pair's head.

Example explanation

Input: A -> B -> C -> D

1. First pair (A, B):
   • B.next points to A.
   • A.next points to the result of swapping (C, D).
2. Second pair (C, D):
   • D.next points to C.
   • C.next points to null (end of list).
3. Final result: B -> A -> D -> C. The "next" pointer of the second node in each pair must be updated to point to the first node, while the first node's "next" pointer is updated to point to the following pair.

Common mistakes candidates make

The most frequent mistake is an "off-by-one" error where the last single node (in an odd-length list) is not handled correctly. Another error is losing the reference to the rest of the list during the swap, causing the list to be truncated. Not updating the "previous" node's next pointer in the iterative approach is also a common pitfall that breaks the chain.

Interview preparation tip

When practicing the Swap Nodes in Pairs interview question, draw the nodes and pointers on paper. Visually tracing the assignments node1.next = node2.next and node2.next = node1 helps ensure you don't skip steps. Also, always use a dummy node for linked list problems where the head might change—it simplifies the logic significantly.