6
6
7
7
#### [ 82. 删除排序链表中的重复元素 II] ( https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/ )
8
8
9
- 题目描述
9
+ ** 题目描述**
10
10
11
11
给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中没有重复出现的数字。
12
12
35
35
36
36
这个题目也是利用我们的双指针思想,一个走在前面,一个在后面紧跟,前面的指针就好比是侦察兵,当发现重复节点时,后面指针停止移动,侦察兵继续移动,直到移动完重复节点,然后将该节点赋值给后节点。思路是不是很简单啊,那么我们来看一下动图模拟吧。
37
37
38
- 注:这里为了表达更直观,所以仅显示了该链表中存在的节点
38
+ 注:这里为了表达更直观,所以仅显示了该链表中存在的节点。
39
39
40
40
![ 删除重复节点2] ( https://cdn.jsdelivr.net/gh/tan45du/photobed@master/photo/删除重复节点2.3btmii5cgxa0.gif )
41
41
@@ -46,28 +46,30 @@ Java Code:
46
46
``` java
47
47
class Solution {
48
48
public ListNode deleteDuplicates (ListNode head ) {
49
- if (head == null || head. next== null ){
50
- return head;
51
- }
49
+ // 侦察兵指针
52
50
ListNode pre = head;
53
- ListNode low = new ListNode (0 );
54
- low. next = pre;
55
- ListNode ret = new ListNode (- 1 );
56
- ret = low;
51
+ // 创建虚拟头节点,接上head
52
+ ListNode dummy = new ListNode (- 1 );
53
+ dummy. next = pre;
54
+ // 跟随的指针
55
+ ListNode low = dummy;
57
56
while (pre != null && pre. next != null ) {
58
57
if (pre. val == pre. next. val) {
58
+ // 移动侦察兵指针直到找到与上一个不相同的元素
59
59
while (pre != null && pre. next != null && pre. val == pre. next. val) {
60
60
pre = pre. next;
61
61
}
62
+ // while循环后,pre停留在最后一个重复的节点上
62
63
pre = pre. next;
64
+ // 连上新节点
63
65
low. next = pre;
64
66
}
65
67
else {
66
68
pre = pre. next;
67
69
low = low. next;
68
70
}
69
71
}
70
- return ret . next;
72
+ return dummy . next;// 注意,这里传回的不是head,而是虚拟节点的下一个节点,head有可能已经换了
71
73
}
72
74
}
73
75
```
@@ -78,29 +80,88 @@ C++ Code:
78
80
class Solution {
79
81
public:
80
82
ListNode* deleteDuplicates(ListNode* head) {
81
- if(head == nullptr || head->next == nullptr){
82
- return head;
83
- }
83
+ //侦察兵指针
84
84
ListNode * pre = head;
85
- ListNode * low = new ListNode(0);
86
- low->next = pre;
87
- ListNode * ret = new ListNode(-1);
88
- ret = low;
85
+ //创建虚拟头节点,接上head
86
+ ListNode * dummy = new ListNode(-1, head);
87
+ dummy->next = pre;
88
+ //跟随的指针
89
+ ListNode * low = dummy;
89
90
while(pre != nullptr && pre->next != nullptr) {
90
91
if (pre->val == pre->next->val) {
92
+ //移动侦察兵指针直到找到与上一个不相同的元素
91
93
while (pre != nullptr && pre->next != nullptr && pre->val == pre->next->val) {
92
94
pre = pre->next;
93
95
}
96
+ //while循环后,pre停留在最后一个重复的节点上
94
97
pre = pre->next;
98
+ //连上新节点
95
99
low->next = pre;
96
100
}
97
101
else{
98
102
pre = pre->next;
99
103
low = low->next;
100
104
}
101
105
}
102
- return ret ->next;
106
+ return dummy ->next;//注意,这里传回的不是head,而是虚拟节点的下一个节点,head有可能已经换了
103
107
}
104
108
};
105
109
```
106
110
111
+ JS Code:
112
+
113
+ ```javascript
114
+ var deleteDuplicates = function(head) {
115
+ //侦察兵指针
116
+ let pre = head;
117
+ //创建虚拟头节点,接上head
118
+ let dummy = new ListNode(-1);
119
+ dummy.next = pre;
120
+ //跟随的指针
121
+ let low = dummy;
122
+ while(pre != null && pre.next != null) {
123
+ if (pre.val == pre.next.val) {
124
+ //移动侦察兵指针直到找到与上一个不相同的元素
125
+ while (pre != null && pre.next != null && pre.val === pre.next.val) {
126
+ pre = pre.next;
127
+ }
128
+ //while循环后,pre停留在最后一个重复的节点上
129
+ pre = pre.next;
130
+ //连上新节点
131
+ low.next = pre;
132
+ }
133
+ else{
134
+ pre = pre.next;
135
+ low = low.next;
136
+ }
137
+ }
138
+ return dummy.next;//注意,这里传回的不是head,而是虚拟节点的下一个节点,head有可能已经换了
139
+ };
140
+ ```
141
+
142
+ Python Code:
143
+
144
+ ``` py
145
+ class Solution :
146
+ def deleteDuplicates (self , head : ListNode) -> ListNode:
147
+ # 侦察兵指针
148
+ pre = head
149
+ # 创建虚拟头节点,接上head
150
+ dummy = ListNode(- 1 , head)
151
+ # 跟随的指针
152
+ low = dummy
153
+ while pre is not None and pre.next is not None :
154
+ if pre.val == pre.next.val:
155
+ # 移动侦察兵指针直到找到与上一个不相同的元素
156
+ while pre is not None and pre.next is not None and pre.val == pre.next.val:
157
+ pre = pre.next
158
+ # while循环后,pre停留在最后一个重复的节点上
159
+ pre = pre.next
160
+ # 连上新节点
161
+ low.next = pre
162
+ else :
163
+ pre = pre.next
164
+ low = low.next
165
+ return low.next # 注意,这里传回的不是head,而是虚拟节点的下一个节点,head有可能已经换了
166
+ ```
167
+
0 commit comments