82. 删除排序链表中的重复元素 II

题意

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的

数字 。返回 已排序的链表 。

难度

中等

示例

示例 1：

082.%E5%88%A0%E9%99%A4%E6%8E%92%E5%BA%8F%E9%93%BE%E8%A1%A8%E4

%B8%AD%E7%9A%84%E9%87%8D%E5%A4%8D%E5%85%83%E7%B4%A0II-20230928

104041.png

输入：head = [1,2,3,3,4,4,5]

输出：[1,2,5]

示例 2：

082.%E5%88%A0%E9%99%A4%E6%8E%92%E5%BA%8F%E9%93%BE%E8%A1%A8%E4

%B8%AD%E7%9A%84%E9%87%8D%E5%A4%8D%E5%85%83%E7%B4%A0II-20230928

104052.png

输入：head = [1,1,1,2,3]

输出：[2,3]

分析 1

注意：本题并不是把重复的节点删掉只剩一个，而是所有重复的节点全部删掉。

首先我们能想到的就是，利用一个 HashMap 来记录使用过的元素个数，出现一次增加

1，然后再重新遍历整个链表，留下个数为 1 的元素，其余的全都删除。

或者换个方法，将个数为 1 的加入到新的链表，最后再把新的链表作为结果返回。

OK，我们就来按照这样的思路试一次，链表已经定义好了，见下面注释中的代码，

LeetCode 只需要们写出题解就行了。

/**

* 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; }

*}

*/

class Solution {

public ListNode deleteDuplicates(ListNode head) {

// 1. 若链表为空，则直接返回 null

if (head == null) {

return null;

}

// 2. 创建一个映射来存储链表中的每个值及其出现的次数

 HashMap<Integer,Integer> map = new HashMap<>();

ListNode cur = head;

// 3. 遍历链表，统计每个元素出现的次数

while(cur != null) {

map.put(cur.val,map.getOrDefault(cur.val,0) + 1);

cur = cur.next;

}

// 4. 创建一个新的伪头节点以帮助后续链表的构建

ListNode grandFather = new ListNode(0,null);

ListNode temp = grandFather; // 用于最后返回结果的伪头节点的引用

cur = head; // 将 cur 重新指向原始链表的头部

// 5. 遍历原始链表，查看映射中的值，将出现一次的元素添加到新链表

while(cur != null) {

if (map.get(cur.val) == 1) {

grandFather.next = new ListNode(cur.val,null);

grandFather = grandFather.next; // 移动 grandFather 到新链表的尾部

}

cur = cur.next; // 移动原始链表的指针

}

// 6. 返回新链表的头部（跳过伪头节点）

return temp.next;

}

}

我们来模拟一下整个过程：

初始链表为: 1 -> 1 -> 2 -> 3 -> 3 -> 4

经过第一轮的 HashMap 处理后，我们知道数字 1 和 3 是重复的，所以只有 2 和 4 会被添

加到新链表中。

下面是 grandFather 在新链表构建过程中的状态变化图解：

1. 初始化：

grandFather(dummy node)

↓

[0]

这是一个伪头节点，用于方便地开始构建新的链表。

2. 当处理到值为 2 的节点时:

grandFather(dummy node) New Node

↓ ↓

[0] -> [ 2 ]

我们创建了一个新节点并将其添加到 grandFather 的后面。

3. 更新**grandFather**的位置:

(dummy node) grandFather

↓ ↓

[0] -> [ 2 ]

现在 grandFather 已经移到了新链表的末尾。

4. 当处理到值为 4 的节点时:

(dummy node) grandFather New Node

↓ ↓ ↓

[0] -> [ 2 ] -> [ 4 ]

我们再次创建一个新节点并将其添加到 grandFather 的后面。

5. 更新**grandFather**的位置:

(dummy node) (old grandFather) grandFather

↓ ↓ ↓

[0] -> [ 2 ] -> [ 4 ]

再次更新 grandFather 的位置，使其始终指向新链表的尾部。

最终，新链表为: 2 -> 4

运行效率如下所示：

082.%E5%88%A0%E9%99%A4%E6%8E%92%E5%BA%8F%E9%93%BE%E8%A1%A8%E4

%B8%AD%E7%9A%84%E9%87%8D%E5%A4%8D%E5%85%83%E7%B4%A0II-20230928

105128.png

看情况不太乐观，因为我们需要遍历两次链表，而且空间占用也不理想，需要用到一个新

的链表和 HashMap。怎么办呢？

注意题目的特性——已排序的链表，也就是说，如果有重复的元素，必然是连着一起出现

的，所以我们就可以利用链表的特性，直接跳过这一片节点。

这一次，我们利用一个 grandFather 作为原先头节点的父节点，就从这个 grandFather

（cur）开始遍历，因为原先的头节点如果是重复元素，也是要被删除的。

接着遍历整个链表，如果 cur.next.val==cur.next.next.val，就说明接下来的一片节点

都是相同的元素，我们只需要记录当前的 val，然后把 cur.next 替换成 cur.next.next，

就可以完成对 cur.next 的无缝删除，也就不需要用到新的存储空间和遍历时间了。

/**

* 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; }

*}

*/

class Solution {

public ListNode deleteDuplicates(ListNode head) {

// 判断头节点是否为空，如果为空直接返回 null。

if (head == null) {

return null;

}

// 初始化 grandFather 和 cur 为同一个虚拟节点，该虚拟节点的 next 指向 head

ListNode grandFather = new ListNode(0, head);

ListNode cur = grandFather;

// 循环遍历链表，直至链表结束或者是链表的最后一个节点

while (cur.next != null && cur.next.next != null) {

// 判断当前节点与其后续节点的值是否相等，如果相等，说明有重复

if (cur.next.val == cur.next.next.val) {

int val = cur.next.val;

// 移动 cur 的下一个指针，直至找到与 val 不同的值的节点，或者到链表末尾

while (cur.next != null && cur.next.val == val) {

cur.next = cur.next.next;

}

} else {

// 如果当前节点与其后续节点的值不相等，则直接移动 cur 指针

cur = cur.next;

}

}

// 返回删除重复之后的链表头部，由于我们初始化 grandFather 的 next 为 head，所以

这里返回 grandFather.next

return grandFather.next;

}

}

再以一个例子来进行说明：

给定链表: 1 -> 2 -> 2 -> 3 -> 4 -> 4 -> 5

• 初始化 grandFather 和 cur 指向虚拟节点。

• 当遍历到第一个 2 时，检测到它与下一个 2 是重复的，因此进入内部的 while 循环，

持续移动 cur.next，直到它指向了 3。

• 当遍历到第一个 4 时，同样检测到重复，将 cur.next 移动，直至指向 5。

• 最后，返回 grandFather.next，即结果链表：1 -> 3 -> 5。

来看这一次的题解效率，果然比上一次的好多了：

082.%E5%88%A0%E9%99%A4%E6%8E%92%E5%BA%8F%E9%93%BE%E8%A1%A8%E4

%B8%AD%E7%9A%84%E9%87%8D%E5%A4%8D%E5%85%83%E7%B4%A0II-20230928

110711.png

分析 2

我们还可以使用递归来解决这个问题。递归的主要思想是：

• 如果链表为空或只有一个元素，直接返回链表。

• 如果当前元素与下一个元素相同，跳过所有重复的元素。

• 如果当前元素与下一个元素不同，递归地处理后续的链表，并将当前元素与处理后的

链表连接起来。

public class Solution {

public ListNode deleteDuplicates(ListNode head) {

// 如果链表为空或只有一个元素，直接返回

if (head == null || head.next == null) {

return head;

}

// 如果当前元素与下一个元素相同

if (head.val == head.next.val) {

// 跳过所有重复的元素

while (head.next != null && head.val == head.next.val) {

head = head.next;

}

// 递归处理后续的链表

return deleteDuplicates(head.next);

} else {

// 如果当前元素与下一个元素不同

// 递归地处理后续的链表，并连接当前元素

head.next = deleteDuplicates(head.next);

return head;

}

 }

}

运行效率如下所示：

082.%E5%88%A0%E9%99%A4%E6%8E%92%E5%BA%8F%E9%93%BE%E8%A1%A8%E4

%B8%AD%E7%9A%84%E9%87%8D%E5%A4%8D%E5%85%83%E7%B4%A0II-20230928

111408.png

总结

链表是最基础的数据结构之一，也是算法题的重中之重，抓住题目的细节（排序的链

表），才能突破瓶颈。

力扣链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/

更新: 2023-09-28 03:16:51

原文: https://www.yuque.com/itwanger/czfoq9/qvtgt6