返回

[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 进行检查

代码如下:

/**
 * 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

Built with Hugo
Theme Stack designed by Jimmy