Reference: LeetCode
Difficulty: Medium

Problem

Given a linked list, swap every two adjacent nodes and return its head.

Note: You may not modify the values in the list’s nodes, only nodes itself may be changed.

Example:

1
Given 1->2->3->4, you should return the list as 2->1->4->3.

Analysis

Test Case:

1
2
3
4
5
6
7
8
9
10
11
12
// 1
[1]
[1]
// 2
[1,2]
[2,1]
// 3
[1,2,3]
[2,1,3]
// 4
[1,2,3,4]
[2,1,4,3]

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// prev -> head -> t -> nextTemp
// prev -> t -> head -> nextTemp
ListNode t = head.next;
ListNode nextTemp = head.next.next; // head.next is not null
head.next = swapPairs(nextTemp);
t.next = head;
return t;
}

Time: $O(N)$
Space: $O(N)$

Iteration

Note: Use this template for most iterative methods:

1
2
3
4
5
6
7
8
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode p = head; // or use curr
ListNode prev = dummy; // act as a sentinel
while (p != null) { // p != null or p.next != null
// ...
}
return dummy.next;

If I use p.next as a left-value in the block code, I have to indicate in the while condition that p.next != null. And usually, p != null and p.next != null are together.

Update prev before updating p.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode dummy = new ListNode(0); // since head might be swapped
ListNode prev = dummy;
ListNode p = head;
// dummy -> 1 -> 2 -> 3 -> 4
// prev p t nextTemp
// prev t p
while (p != null && p.next != null) { // p.next is not necessary since each time move by 2 steps
ListNode t = p.next;
ListNode nextTemp = p.next.next;
prev.next = t;
t.next = p;
p.next = nextTemp;
// update
prev = p;
p = nextTemp;
}
return dummy.next;
}

Time: $O(N)$
Space: $O(1)$


Comment