0%

将链表根据条件分区

简介

将链表根据条件分为左中右三部分, 确保左边链表小于条件值, 中间的链表等于条件值, 右边的链表大于条件值

分析

通过简单的标识将链表划分为三个子链表, 然后再拼接起来, 可以简单实现

实现

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
public class ListPartition {
@RequiredArgsConstructor
@AllArgsConstructor
static class Node {
@NonNull
int value;
public Node next;
}

/**
* 将链表按照标识分区
* @param node
* @param flag
* @return
*/
static Node listPartition(Node node, int flag) {
// small 链表表头标识
Node sH = null;
// small 链表表尾标识
Node sT = null;
// equal 链表表头标识
Node eH = null;
// equal 链表表尾标识
Node eT = null;
// big 链表表头标识
Node bH = null;
// big 链表表尾标识
Node bT = null;
// 保存下一个节点
Node next;
// 循环判断并将节点分别加入三个链表中
while (node != null) {
next = node.next;
node.next = null;
if (node.value < flag) {
if (sH == null) {
sH = node;
sT = node;
} else {
// 将符合的节点链接到后面并将表尾指向当前节点
sT.next = node;
sT = node;
}
} else if (node.value == flag) {
if (eH == null) {
eH = node;
eT = node;
} else {
eT.next = node;
eT = node;
}
} else {
if (bH == null) {
bH = node;
bT = node;
} else {
bT.next = node;
bT = node;
}
}
node = next;
}
if (sT != null) {
// 链接 equal 链表
sT.next = eH;
// 如果 equal 链表不存在, 则将 equal 链表的表尾指向 small 链表
eT = eT == null ? sT : eT;
}
if (eT != null) {
// 链接 big 链表
eT.next = bH;
}
// 返回存在的链表
return sH != null ? sH : eH != null ? eH : bH;
}

public static void main(String[] args) {
Node node = new Node(7
, new Node(9
, new Node(3
, new Node(8
, new Node(5
, new Node(2
, new Node(5)))))));
node = listPartition(node, 5);
while (node != null) {
System.out.printf(node.value + " > ");
node = node.next;
}
}
}

结果

1
2
3 > 2 > 5 > 5 > 7 > 9 > 8 >
Process finished with exit code 0