删除排序链表中的重复元素【文末附思维导图】
删除排序链表中的重复元素【文末附思维导图】
一.题目
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1: 输入: 1->1->2 输出: 1->2
示例 2: 输入: 1->1->2->3->3 输出: 1->2->3
二.解题方法
1.循环遍历法
思路
题目中有一个特殊且重要的条件，就是排序，这个链表是已经排好序的，那么如果存在相同的元素，一定是相邻的节点，这就好办了，我们可以通过遍历一次链表，在遍历过程中判断当前节点的 val 和下一个节点的 val 是不是相等，如果相等则删除下个节点，以此类推，直到遍历完链表。
代码
/**
* 循环遍历法
*/
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode current = head;
while (current.next != null) {
if (current.val == current.next.val) {
current.next = current.next.next;
} else {
current = current.next;
}
}
return head;
}
时间复杂度
我们只需要遍历一遍链表，所以是 O(n)。
空间复杂度
代码中我们可以看到只有一个 current 来记录，没有其他额外的空间使用，所以是 O(1)。
2.递归法
思路
和上面循环遍历法的思路一样，但是换成递归的实现方式，一个算法要用递归实现需要满足 3 个条件，下面通过这 3 个条件来确认这个题是否可以用递归实现。
- 一个问题的解可以分解为几个子问题的解 很明显，这个题可以，把删除一个链表的重复数据分解成删除几个子链表的重复数据
- 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样 这个也可以肯定，子链表数据规模小了，但是还是一样的思路：删除重复数据
- 存在递归终止条件 当遍历到链表最后一个节点则终止
分析完确认可以通过递归完成，那么下面看代码。
代码
/**
* 递归法
*/
public ListNode deleteDuplicates2(ListNode head) {
if (head == null || head.next == null) {
return head;
}
if (head.next != null) {
if (head.val == head.next.val) {
return deleteDuplicates(head.next);
} else {
head.next = deleteDuplicates(head.next);
}
}
return head;
}
时间复杂度
依旧是遍历一次链表，所以是 O(n)。
空间复杂度
没有使用多余的空间，也就是常数复杂度，也用 O(1) 表示。
3.HashSet 法
这个方法可以摆脱排序这个特性，即使是没有排序的链表，也可以使用这个方法。使用 HashSet，记录遍历过的每个节点的值，判断下一个节点是否已经存在于 HashSet，存在的就删除掉，不存在的就继续遍历下一个。这个方法效率也是不错的，因为通过 HashSet 存取数据的效率都不错。
代码
/**
* HashSet 法
*/
public ListNode deleteDuplicates3(ListNode head) {
if (head == null || head.next == null) {
return head;
}
Set<Integer> container = new HashSet<>();
ListNode current = head;
while (current.next != null) {
// 当前节点值先放入 Set 容器
container.add(current.val);
// 检查下一个节点的值是否存在 Set 容器中
if (container.contains(current.next.val)) {
current.next = current.next.next;
} else {
current = current.next;
}
}
return head;
}
时间复杂度
这个和之前方法多了数据查询和存储进 HashSet 的开销，但是查询 HashSet 的实现复杂度是 O(1)，存数据到 HashSet 的复杂度也是 O(1)，所以依旧是遍历一次链表的时间复杂度开销大，整个操作的时间复杂度依旧是 O(n)。
空间复杂度
利用了 HashSet 容器来存储每个节点，所以空间复杂度是 O(k)(k <= n)，也就是用 O(n) 表示。
> 附思维导图原件：https://mubu.com/doc/xwfVFiHQs0
> 或者扫描二维码：
