Question

LeetCode Link | 24. Swap Nodes in Pairs | Medium

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list’s nodes (i.e., only nodes themselves may be changed.)

Constraints

  • The number of nodes in the list is in the range [0, 100]
  • 0 <= Node.val <= 100

Examples

Example 1

Example 1

Input: head = [1,2,3,4]
Output: [2,1,4,3]

Example 2

Input: head = []
Output: []

Example 3

Input: head = [1]
Output: [1]

Solution Approach

Method: Manual / Simulate

Constrains

  • None

This method does not have any limitations.

Concept Explanation

Let’s break this question into a smaller one, how to swap two node?

The answer is simple, just set the secondNode.next to the firstNode.

swap two nodes

What if there are more than one pairs in the Linked List?

Fix next connection

Firstly, we will need to fix the connections between pairs. If we have a list [1, 2, 3, 4], after swap it becomes [2, 1, 3, 4] but 1.next is still point to 2. Thus, we need to set 1.next to 3 which is the third node, and it becomes as follow:

1
2
3
4
5
// Swap the nodes in pairs
secondNode.next = firstNode;

// Fix the next pointer of the pair
firstNode.next = thirdNode;

What if the pair is not the first pair?

if we handling the second pair [3, 4], we will find that the next pointer of the previous pair is also wrong, which means we have to set 1.next to 4 to meet the complete list [2, 1, 4, 3].

Fix previous connection

This cause the code has two condition:

  • If this is the first pair, we don’t need to fix the previous pair’s next pointer.
  • Otherwise, fix the connection.

To make logic simple and unify, we could use a dummy node to solve this question. By adding a dummy node before the head node, every pair no longer a first pair.

Unify Logic

Finally, return the head node after swaping all pairs by returning dummyNode.next as we mentioned dummy node is ahead of the head node.

Code

  • Time complexity: O(n)
  • Space complexity: O(1)

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function swapPairs(head: ListNode | null): ListNode | null {
	// Create a dummy node to point to the head
	const dummyNode = new ListNode(0, head);

	// Create an iterator node to point to the dummy node
	let curNode = dummyNode;

	// Iterate through the linked list
	while (curNode && curNode.next && curNode.next.next) {
		const firstNode = curNode.next;
		const secondNode = curNode.next.next;
		const thirdNode = curNode.next.next.next;

		// Swap the nodes in pairs
		secondNode.next = firstNode;

		// Fix the next pointer of the pair
		firstNode.next = thirdNode;

		// Fix the next pointer of the previous pair
		curNode.next = secondNode;

		// Go to the next pair
		curNode = firstNode;
	}
	return dummyNode.next;
};

Conclusion

This question can also be implement using the recursion since this is a unified loop. Remember that the graph is always your friend, if you can not figure out the logic clearly, just draw a graph. Never start to code without a clear logic, or you are gonna messed up your code.