0%

[Leetcode]82. Remove Duplicates from Sorted List II(C++)

题目描述

题目链接: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++) 类似,同样是去除链表中的重复项,但要求所有重复节点都去除而不是保留一个。因此在上一题的逻辑上需要进行以下修改:

  • prevcurr 分别代表前一节点和当前要检查的节点
  • curr 开始往后遍历知道某一时刻, curr->val != curr->next->val,此时已经跳过所有有重复值的节点,将prev->next 指向当前的 curr->next 即可(curr->next 为空也可以)
  • 注意:当找到有重复项时,完成连接后不能直接将 prevcurr 直接向后迭代一步,而是应该对新的 prev->next 进行检查

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
* 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