LeetCode-82-删除链表重复元素②
1. 题目描述
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
1
2
3
4
5
6
7
8
9
| 示例 1:
输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例 2:
输入: 1->1->1->2->3
输出: 2->3
|
2. 思路
这个题的简答版本就是删除链表的重复元素(LeetCode-83-删除链表重复元素)[https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/]，让每个元素最多出现一次，这个版本是比较简单的。最开始我是没看到这个链表是有序的前提，所以直接用个map统计每个元素出现的次数，如果之前出现过这个元素就把这个删掉，后来发现是有序的，所以是无需这个map的。
本题的不同点在于只要有重复出现，那么这个元素的就不再保留在链表中，这肯定是双指针思路，让快指针去找，慢指针来挂结点，记录这篇的目的是学习一下别人优雅的代码。
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
|
public class DeleteDuplicates82 {
public ListNode deleteDuplicates82(ListNode head) {
ListNode cur = head;
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode fast, slow;
slow = dummy;
fast = head;
if (head == null)
return null;
while (fast != null) {
if (fast.next == null || fast.val != fast.next.val) {
if (slow.next == fast) {
slow = fast;
} else {
slow.next = fast.next;
}
}
fast = fast.next;
}
return dummy.next;
}
}
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
|
