题目描述
题目链接:82. Remove Duplicates from Sorted List II
Given the
head
of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.
例子
例子 1
Input:
head = [1,2,3,3,4,4,5]
Output:[1,2,5]
例子 2
Input:
head = [1,1,1,2,3]
Output:[2,3]
Constraints
- The number of nodes in the list is in the range
[0, 300]
.-100 <= Node.val <= 100
- The list is guaranteed to be sorted in ascending order.
解题思路
跟 [Leetcode]83. Remove Duplicates from Sorted List(C++) 类似,同样是去除链表中的重复项,但要求所有重复节点都去除而不是保留一个。因此在上一题的逻辑上需要进行以下修改:
- 用
prev
和curr
分别代表前一节点和当前要检查的节点 - 从
curr
开始往后遍历知道某一时刻,curr->val != curr->next->val
,此时已经跳过所有有重复值的节点,将prev->next
指向当前的curr->next
即可(curr->next
为空也可以) - 注意:当找到有重复项时,完成连接后不能直接将
prev
和curr
直接向后迭代一步,而是应该对新的prev->next
进行检查
代码如下:
1 | /** |
- 时间复杂度: O(n)
- 空间复杂度: O(1)
GitHub 代码同步地址: 82.RemoveDuplicatesFromSortedListIi.cpp
其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions