【每日一题】删除排序链表中的重复元素 II

Tag

【遍历链表】【链表】【2024-01-15】

---

题目来源

82. 删除排序链表中的重复元素 II

---

解题思路

几乎所有链表的题目都可以先将链表转成数组，再对数组执行操作，最后将数组还原回链表。这样操作确实会麻烦一点，适用于直接处理链表比较困难或易错的情况。这是一种处理思路，多见于算法初学者做题时。在熟悉链表基础操作之后，可以直接对链表进行相应操作。

接下来看一看如何直接处理链表。

方法一：遍历链表

思路

因为给定的链表是排好序的，所以重复的链表元素在链表中的位置一定是连续的。我们只需要对链表进行一次遍历，就可以删除链表中重复的元素。由于链表的头结点可能被删除，因此需要使用一个 哑结点 指向链表的头结点。

具体实现中，我们从哑结点开始对链表进行遍历。如果当前节点 cur 的下一个和下下个节点对应的元素相同，那么我们需要将 cur->next 以及后面所有拥有相同元素值的链表节点全部删除。我们将这个元素值记为 x，随后不断将 cur->next 从链表中移除，直至 cur->next 为空节点或者其元素值不等于 x 为止。此时，链表中元素值等于 x 的节点全部被移除。

如果当前节点 cur 的下一个和下下个节点对应的元素相同，那么说明 cur->next 节点的元素值不是重复的，保留，将 cur 指向 cur->next。

最后返回 dummy->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) {
        if(head == nullptr || head->next == nullptr) {
            return head;
        }

        // 有可能头结点是重复出现的，因此搞一个哑结点
        ListNode *dummyNode = new ListNode(0, head);
        ListNode *curr = dummyNode;

        while(curr->next && curr->next->next) {
            if (curr->next->val == curr->next->next->val) {
                int x = curr->next->val;
                while (curr->next && curr->next->val == x) {
                    curr->next = curr->next->next;
                }
            }else{
                curr = curr->next;
            }
        }
        return dummyNode->next;
    }
};

复杂度分析

时间复杂度：$O(n)$，$n$ 是链表的长度。

空间复杂度：$O(1)$。

---

写在最后

如果您发现文章有任何错误或者对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度的方法，欢迎评论区交流。

最后，感谢您的阅读，如果有所收获的话可以给我点一个 👍 哦。