XTAO's Tech Blog
0%

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

发表于 更新于 分类于 ， 评论数：
1.6k 1 分钟

题目描述

题目链接：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
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

推荐文章