数据结构第一节就是链表。链表由多个node节点组成，每个node节点包含数据和一个指针。指针指向下一个节点。
组装链表
经常问单链表的算法，那你首先要定下来链表的结构，而不是直接思考算法。为了方便使用，我们固定一个哨兵作为
头节点。数据节点都在头节点之后。
1
2
3
4
5
6
7
8
9
10
|
@Data
static class Node {
private Boolean head;
private Integer data;
private Node next;
}
|
那么，我们创建的一个节点是这样的
1
2
3
4
5
6
7
| Node head = new Node();
head.setData(-1);
head.setHead(true);
Node node = new Node();
node.setData(123);
node.setHead(false);
|
所以，我们首先要创建一个数组1 2 3 4 5 6 7 8 9。
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
|
private Node toNode(Integer[] arr) {
Node head = new Node();
head.setData(-1);
head.setHead(true);
Node tail = head;
for (int i = 0; i < arr.length; i++) {
Node node = new Node();
node.setData(arr[i]);
node.setNext(null);
node.setHead(false);
tail.next = node;
tail = node;
}
return head;
}
private Node makeNode(Integer... arr) {
return toNode(arr);
}
makeNode(1,2,3,4,5,6,7,8,9);
|
为了方便展示，写一个链表遍历的方法，用来打印链表结构：
1
2
3
4
5
6
7
8
9
10
11
| private static void printNode(Node head) {
Node p = head.next;
while (p != null) {
System.out.print(p.getData());
p = p.next;
if (p != null) {
System.out.print("->");
}
}
System.out.println();
}
|
链表插入
插入节点tmp. 先找到要插入的位置，然后构造插入节点tmp。让tmp指向后面的节点。前一个节点指向tmp。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| @Test
public void testInsert() {
Node node = makeNode(3, 4, 5, 6, 7, 8, 9);
System.out.println("--------origin--------");
printNode(node);
Node p = node;
while (p != null) {
if (p.getData() == 4) {
Node tmp = new Node();
tmp.setData(10);
tmp.next = p.next;
p.next = tmp;
break;
}
p = p.next;
}
System.out.println("--------inserted--------");
printNode(node);
}
|
打印结果：
1
2
3
4
| --------origin--------
3->4->5->6->7->8->9
--------inserted--------
3->4->10->5->6->7->8->9
|
链表删除
链表删除首先要找到要删除的节点，将pre指向next。
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
| @Test
public void deleteNode() {
Node node = makeNode(3, 4, 5, 6, 7, 8, 9);
System.out.println("--------origin--------");
printNode(node);
Node head = node;
Node p = node;
while (p != null) {
if (p.getData() == 5) {
head.next = p.next;
break;
}
Node pre = p;
p = p.next;
if (p != null && p.getData().equals(5)) {
pre.next = p.next;
break;
}
}
System.out.println("---------deleted---------");
printNode(head);
}
|
打印结果
1
2
3
4
| --------origin--------
3->4->5->6->7->8->9
---------deleted---------
3->4->6->7->8->9
|
链表反转
链表最常问的算法就是反转了。目前有两个常见的方式，一个是头插入法，新建一个head，遍历原来的head，插入新链表。
一个是就地反转。将链表看成两部分，左边是新链表，右边是旧链表。每次从右边取出一个，插入左边的头部，最终全部插入左边。实现整体反转。
头插法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| private Node headInsert(Node head) {
if (head.next == null) {
return head;
}
final Node newHead = new Node();
newHead.setHead(true);
newHead.setData(head.getData());
Node p = head;
while (p.next != null) {
Node tmp = p.next;
p.next = p.next.next;
tmp.next = newHead.next;
newHead.next = tmp;
}
return newHead;
}
|
打印结果：
1
2
3
4
| =========origin==========
3->4->5->6->7->8->9
---------head insert--------
9->8->7->6->5->4->3
|
就地反转
原始文件
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
| private Node inverse(Node head) {
if (head == null) {
return null;
}
Node leftTail = head.next;
if (leftTail == null) {
return head;
}
Node pCur = leftTail.next;
if (pCur == null) {
leftTail.next = head;
head.next = null;
return leftTail;
}
while (pCur != null) {
leftTail.next = pCur.next;
pCur.next = head.next;
head.next = pCur;
pCur = leftTail.next;
}
return head;
}
|
打印结果：
1
2
3
4
| =========origin==========
3->4->5->6->7->8->9
---------inverse--------
9->8->7->6->5->4->3
|
完整代码如下：
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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
| package com.test.algorithm.link;
import lombok.Data;
import org.junit.Test;
public class 单链表反转 {
@Data
static class Node {
private Boolean head;
private Integer data;
private Node next;
}
@Test
public void testInsert() {
Node node = makeNode(3, 4, 5, 6, 7, 8, 9);
System.out.println("--------origin--------");
printNode(node);
Node p = node;
while (p != null) {
if (p.getData() == 4) {
Node tmp = new Node();
tmp.setData(10);
tmp.next = p.next;
p.next = tmp;
break;
}
p = p.next;
}
System.out.println("--------inserted--------");
printNode(node);
}
@Test
public void deleteNode() {
Node node = makeNode(3, 4, 5, 6, 7, 8, 9);
System.out.println("--------origin--------");
printNode(node);
Node head = node;
Node p = node;
while (p != null) {
if (p.getData() == 5) {
head.next = p.next;
break;
}
Node pre = p;
p = p.next;
if (p != null && p.getData().equals(5)) {
pre.next = p.next;
break;
}
}
System.out.println("---------deleted---------");
printNode(head);
}
private Node makeNode(Integer... arr) {
return toNode(arr);
}
@Test
public void testInverse() {
Integer[] arr = new Integer[]{
3, 4, 5, 6, 7, 8, 9
};
inverse(arr);
headInsert(arr);
Integer[] arr2 = new Integer[]{
1
};
headInsert(arr2);
inverse(arr2);
Integer[] arr3 = new Integer[]{
1, 2
};
inverse(arr3);
headInsert(arr3);
}
private void headInsert(Integer[] arr) {
Node head = toNode(arr);
System.out.println("=========origin==========");
printNode(head);
Node inverse = headInsert(head);
System.out.println("---------head insert--------");
printNode(inverse);
}
private Node headInsert(Node head) {
if (head.next == null) {
return head;
}
final Node newHead = new Node();
newHead.setHead(true);
newHead.setData(head.getData());
Node p = head;
while (p.next != null) {
Node tmp = p.next;
p.next = p.next.next;
tmp.next = newHead.next;
newHead.next = tmp;
}
return newHead;
}
private void inverse(Integer[] arr) {
Node head = toNode(arr);
System.out.println("=========origin==========");
printNode(head);
Node inverse = inverse(head);
System.out.println("---------inverse--------");
printNode(inverse);
}
private Node toNode(Integer[] arr) {
Node head = new Node();
head.setData(-1);
head.setHead(true);
Node tail = head;
for (int i = 0; i < arr.length; i++) {
Node node = new Node();
node.setData(arr[i]);
node.setNext(null);
tail.next = node;
tail = node;
}
return head;
}
private Node inverse(Node head) {
if (head == null) {
return null;
}
Node leftTail = head.next;
if (leftTail == null) {
return head;
}
Node pCur = leftTail.next;
if (pCur == null) {
leftTail.next = head;
head.next = null;
return leftTail;
}
while (pCur != null) {
leftTail.next = pCur.next;
pCur.next = head.next;
head.next = pCur;
pCur = leftTail.next;
}
return head;
}
private static void printNode(Node head) {
Node p = head.next;
while (p != null) {
System.out.print(p.getData());
p = p.next;
if (p != null) {
System.out.print("->");
}
}
System.out.println();
}
}
|
