-
Notifications
You must be signed in to change notification settings - Fork 13
Expand file tree
/
Copy pathSolution0082.java
More file actions
127 lines (118 loc) · 4.86 KB
/
Copy pathSolution0082.java
File metadata and controls
127 lines (118 loc) · 4.86 KB
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
// 82. 删除排序链表中的重复元素 II
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
/*
递归：
1、方法功能：入参是一个节点，判断该节点是否重复，不重复则返回该节点，否则往下遍历找到第一个与该节点不相同的节点后返回
2、终止条件：节点为空 或 下一节点为空，则直接返回，因为至少需要两个节点才需要判断删除
3、递归逻辑：先根据一个节点的情况进行处理，处理完后下一节点同样需要判断处理，则调用同样的方法递归处理
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
if (head.val != head.next.val) {
head.next = deleteDuplicates(head.next);
return head;
} else {
ListNode temp = head.next;
while (temp != null && head.val == temp.val) {
temp = temp.next;
}
return deleteDuplicates(temp);
}
}
}
/*
一次遍历，改变节点指针：
1、至少要有两个节点才需要判断删除，否则直接返回
2、初始化pre、cur的位置，两者相邻。pre表示前一个有效节点的指针
3、当cur下一节点值与当前相同时，则cur继续往右走，走到最后一个值相同的节点
4、如果pre下一节点还是cur，说明中间没有重复节点，pre往右走一步即可。
如果pre下一节点不是cur，说明中间有重复节点，包括cur在内的节点都要删除，即pre下一指针指向cur下一指针节点。此时pre还不能动，因为新的cur可能还是重复节点
5、经过一轮判断处理后，cur往右走一步。此时pre、cur回到初始状态
0 → 1 → 2 → 3 → 3 → 4 → 4 → 5
root/pre cur
===========================================================
0 → 1 → 2 → 3 → 3 → 4 → 4 → 5
root pre cur
===========================================================
0 → 1 → 2 → 3 → 3 → 4 → 4 → 5
root pre cur
===========================================================
0 → 1 → 2 → 3 → 3 → 4 → 4 → 5
root pre cur
===========================================================
0 → 1 → 2 → 4 → 4 → 5
root pre cur
===========================================================
0 → 1 → 2 → 4 → 4 → 5
root pre cur
===========================================================
0 → 1 → 2 → 5
root pre cur
===========================================================
0 → 1 → 2 → 5
root pre cur
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode root = new ListNode(0, head);
ListNode pre = root, cur = head;
while (cur != null) {
while (cur.next != null && cur.val == cur.next.val) {
cur = cur.next;
}
if (pre.next == cur) {
pre = pre.next;
} else {
pre.next = cur.next;
}
cur = cur.next;
}
return root.next;
}
}
/*
记录个数，改变节点指针：
1、上一解法是cur直接走到最后一个重复节点位置，一次性跳过多个重复节点
当前解法是cur一步一步走，根据map中记录的出现次数决定是否跳过cur节点
2、先遍历一次，记录每个节点值出现次数
3、再次遍历，如果节点出现次数大于1则跳过
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
Map<Integer, Integer> map = new HashMap<>();
ListNode temp = head;
while (temp != null) {
map.put(temp.val, map.getOrDefault(temp.val, 0) + 1);
temp = temp.next;
}
ListNode root = new ListNode(0, head);
ListNode pre = root, cur = head;
while (cur != null) {
if (map.get(cur.val) == 1) {
pre = pre.next;
} else {
pre.next = cur.next;
}
cur = cur.next;
}
return root.next;
}
}