今天是 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