关于链表，近期在刷题的时候发现，它还是有操作的套路可言的，不见得所有的题目都能套上模板，但是已经能解决60-70%的链表题型了。套路模板如下：
- 入参给你个ListNode, 也可以有其他参数，根据条件返回他指定类型的链表。
- 需要临界值的判断。
- （可以建立一个dummp节点），为了简化操作
- 遍历循环 【4.1: 先报值保留下来 4.2:迭代】
- 返回dummp.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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public ListNode xx(ListNode head, int val) {
if (head == null) { return head; } // 如第二点
// 这里是个假数据，简化判断用的 - 如第三点
ListNode dummy = new ListNode(-1);
ListNode node = dummy;
while (head != null) {
// 先把值保留下来 - 如4.1
ListNode temp = head;
// 在迭代 - 如4.2
head = head.next;
// 也可以根据条件提前返回
if (temp.val != val) {
node.next = temp;
temp.next = null;
node = node.next;
}
}
return dummy.next; // 如5
}
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null) { return head; }
// 这里是个假数据，简化判断用的
ListNode dummy = new ListNode(-1);
ListNode node = dummy;
int lastValue = -1;
boolean first = true;
while (head != null) {
// 先把值保留下来
ListNode temp = head;
// 在迭代
head = head.next;
if (first || lastValue != temp.val) {
node.next = temp;
temp.next = null;
if (first) { first = false; }
lastValue = temp.val;
node = node.next;
}
}
return dummy.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
/**
* LeetCode 203
* @param head
* @param val
* @return
*/
public ListNode removeElements(ListNode head, int val) {
if (head == null) { return head; }
// 这里是个假数据，简化判断用的
ListNode dummy = new ListNode(-1);
ListNode node = dummy;
while (head != null) {
// 先把值保留下来
ListNode temp = head;
// 在迭代
head = head.next;
if (temp.val != val) {
node.next = temp;
temp.next = null;
node = node.next;
}
}
return dummy.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
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
/**
* LeetCode 206 翻转链表 - 利用之前节点的值重新创建节点拼接
* @param head
* @return
*/
public ListNode reverseList(ListNode head) {
if (head == null) { return null; }
ListNode resultNode = null;
while (head != null) {
if (resultNode == null) {
resultNode = new ListNode(head.val);
} else {
ListNode temp = new ListNode(head.val);
temp.next = resultNode;
resultNode = temp;
}
head = head.next;
}
return resultNode;
}
/**
* LeetCode 206 翻转链表 - 不重新创建节点
* @param head
* @return
*/
public ListNode reverseList_01(ListNode head) {
if (head == null || head.next == null) return head;
ListNode resultNode = null;
while (head != null) {
ListNode temp = head;
head = head.next;
if (resultNode == null) {
temp.next = null;
resultNode = temp;
} else {
temp.next = resultNode;
resultNode = temp;
}
}
return resultNode;
}
/**
* LeetCode 206
* @param head
* @return
*/
public ListNode reverseList_02(ListNode head) {
if (head == null || head.next == null) { return head; }
ListNode newHead = null;
while (head != null) {
ListNode temp = head.next;
head.next = newHead;
newHead = head;
head = temp;
}
return newHead;
}
/**
* LeetCode 206 递归的解法
* @param head
* @return
*/
public ListNode reverseList_03(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newNode = reverseList_03(head.next);
head.next.next = head;
head.next = null;
return newNode;
}
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
/**
* LeetCode 237 删除一个节点
* @param node
*/
public void _237_deleteNode(ListNode node) {
if (node.next == null) {
node = null;
} else {
node.val = node.next.val;
node.next = node.next.next;
}
}
class Solution {
public ListNode middleNode(ListNode head) {
if (head == null || head.next == null) { return head; }
ListNode slow = head;
ListNode fast = head.next;
while (fast != null) {
if (fast.next == null) { return slow.next; }
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}
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
/**
* LeetCode 141 判断链表是否存在环
* @param head
* @return
*/
public boolean _141_hasCycle(ListNode head) {
if (null == head || null == head.next) { return false; }
ListNode slow = head;
ListNode fast = head.next;
while (slow != null && fast != null) {
if (slow.equals(fast)) return true;
if (fast.next == null) { return false; }
fast = fast.next.next;
slow = slow.next;
}
return false;
}
/**
* LeetCode 141 配合HashMap解题
* @param head
* @return
*/
public boolean _141_hasCycle_01(ListNode head) {
if (null == head || null == head.next) { return false; }
HashMap<ListNode, Integer> map = new HashMap<>();
while (head != null) {
if (map.containsKey(head)) { return true; }
map.put(head, 1);
head = head.next;
}
return false;
}
