图解 LeetCode 链表: 82. Remove Duplicates from Sorted List II

今天是 LeetCode 算法的 第 1 阶段第 2 天 ，这一阶段主要学习链表相关的算法题和链表数据结构。这道题是上一道的升级版。

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Example 1:Input: 1->2->3->3->4->4->5 Output: 1->2->5 Example 2:Input: 1->1->1->2->3 Output: 2->3 LeetCode

分析

移除链表中出现过多次的节点，解这道题的思路也是「水管思路」，对水管进行拆分，重组。链表中可能出现多个重复节点，需要把这些重复的节点全部干掉。列表 L1 = 1-> 1-> 2 中第 1 个节点和第 2 个节点重复，移除，把第 3 个节点接到根节点的后面：

列表 L1 = 1-> 1-> 1 中所有节点重复，需要都移除：

代码

因为链表是有序的，重复的节点可能有多个，只有当前节点即不等于上一个节点也不等于下一个节点的值，才不重复，所以遍历的时候需要记住上一个重复的节点。C++ 实现如下：

结果

Runtime: 8 ms, faster than 100.00% of C++ online submissions for Remove Duplicates from Sorted List II. Memory Usage: 9.3 MB, less than 13.11% of C++ online submissions for Remove Duplicates from Sorted List II.

总结

如果把链表换成数组，你是不是就觉得非常简单了呢？由于单链表不能直接获取某个节点的上一个节点，所以我们创建了一个节点用来记录上一个节点，避免多次遍历。

下一道题目留给你思考：

21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists. Example: Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4 LeetCode