82. 删除排序链表中的重复元素 II
题目描述
给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
示例
题解
首先，链表是排序过的，所以相同的节点肯定是连续的，只需要遍历一遍就能把所有相同的节点删除
记pre为去重链表的遍历节点itr的前一个节点。（我们从前往后遍历，前面的链表就是去除过后的链表）
- 如果itr.val == itr.next.val，那我们就记flag为当前遍历节点的值，令
flag=itr.val，不断向后遍历令itr = itr.next，直到，itr.next.val != flag 或者 itr.next == null。然后让pre.next = itr.next - 如果itr.val != itr.next.val，那么就说明itr不是冗余节点，则不必删除，让pre = itr即可
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution{
public ListNode deleteDuplicates(ListNode head){
int flag = -101;
ListNode dummyNode = new ListNode();
dummyNode.next = head;
ListNode pre = dummyNode;
ListNode itr = pre.next;
while(itr != null && itr.next != null){
if(itr.val == itr.next.val){
flag = itr.val;
while(itr.next != null && itr.next.val == flag){
itr = itr.next;
}
pre.next = itr.next;
itr = pre.next;
}else{
pre = itr;
itr = itr.next;
}
}
return dummyNode.next;
}
}
|
时间复杂度 O(n), 空间复杂度O(1)
总结
链表的题通常需要注意两点：
- 舍得用变量，千万别想着节省变量，否则容易被逻辑绕晕
- head 有可能需要改动时，先增加一个 假head，返回的时候直接取 假head.next，这样就不需要为修改 head 增加一大堆逻辑了。