链表上怎么解决荷兰国旗问题呢？
1. 使用数组
把链表放在数组中，在数组中解决这个问题，然后再用链表串起来。这个做法比较容易，这里直接给出代码。
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
| public class DutchNationalFlagProblemOnLinkedList1 {
public static ListNode solve(ListNode head) {
int i = 0;
ListNode cur = head;
if(head == null) return null;
for(; cur != null; ++i, cur = cur.next);
int[] help = new int[i];
for(cur = head, i = 0; cur != null; help[i++] = cur.val, cur = cur.next);
int l = -1, r = i;
i = 0;
while(i < r) {
if(help[i] == 0) swap(i++, ++l, help);
else if(help[i] == 2) swap(--r, i, help);
else ++i;
}
for(cur = head, i = 0; cur != null; cur.val = help[i++], cur = cur.next);
return head;
}
static void swap(int i, int j, int[] arr) {
if(i != j && arr[i] != arr[j]) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
static class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
}
|
这样做的空间复杂度是$O(N)$，下面介绍一种更省空间的方法。
2. 原地调整
我们遍历原链表，把0，1和2分别放在一个链表里，然后把这三条链表首尾连接即可。在代码里如何创建一个链表呢？如果使用java.util.LinkedList;的话，空间复杂度也会是$O(N)$；其实在这个题目中，表示一个链表，只需要一个首尾指针即可。如下图所示：
代码如下：
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
41
42
43
44
45
| public class DutchNationalFlagProblemOnLinkedList2 {
public static ListNode solve(ListNode head) {
if(head == null) return null;
ListNode head0 = null,
tail0 = null,
head1 = null,
tail1 = null,
head2 = null,
tail2 = null,
cur = head;
while(cur != null) {
if(cur.val == 0) {
if(head0 == null) head0 = tail0 = cur;
else tail0 = tail0.next = cur;
}else if(cur.val == 1) {
if(head1 == null) head1 = tail1 = cur;
else tail1 = tail1.next = cur;
}else {
if(head2 == null) head2 = tail2 = cur;
else tail2 = tail2.next = cur;
}
cur = cur.next;
}
ListNode join = tail0, ans = head0;
if(join != null) {
join.next = head1;
if(head1 != null) join = tail1;
}else {
ans = head1;
join = tail1;
}
if(join != null) join.next = head2;
else ans = head2;
return ans;
}
static class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
}
|
时间复杂度$O(N)$，空间复杂度$O(1)$。
