题目描述
题目链接: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
进行检查
代码如下:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode *dummy = new ListNode();
dummy->next = head;
ListNode *curr = head, *prev = dummy;
while (curr) {
bool is_distinct = true;
while (curr->next && curr->val == curr->next->val) {
curr = curr->next;
is_distinct = false;
}
if (!is_distinct) {
prev->next = curr->next;
curr = prev->next;
}
else {
prev = prev->next;
curr = prev->next;
}
}
return dummy->next;
}
};
- 时间复杂度: O(n)
- 空间复杂度: O(1)
GitHub 代码同步地址: 82.RemoveDuplicatesFromSortedListIi.cpp
其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions