题解 | #删除有序链表中重复的元素-II#

描述

给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。
首先提出这个题比较不严谨的地方，代码中一开始给出的注释中，结构体的定义是不严谨的，虽然注释中定义的结构体是下面的样子

/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 */

这样定义的结构体，因为没有构造函数，所以需要通过 malloc 函数来申请空间，但是实际上它真正的定义是下面的样子，

struct ListNode{
    int val;
    struct ListNode* next;
    ListNode(int x, ListNode* next) : val(x), next(nullptr) {}
};

这样定义的结构体可以通过 new 关键字比较方便地初始化，这里的确别会有一些误导读者，特指出。

方法一

遍历一次删除重复的节点。

我们通过 pre->next 和 pre->next->next 的值来确定是否有重复值，下面情况就没有重复值

下面的情况就是有重复值的情况，这样的情况我们可以通过一个循环确定出下一个不是当前重复值的节点，然后让 pre 的 next 成员指向它。

代码实现

// c++
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode *fake = new ListNode(0), *pre = fake;
        fake->next = head;
        while (pre->next) {
            int t = pre->next->val;
            ListNode* tmp = pre->next;
            if (tmp->next && tmp->val == tmp->next->val) { // 这里判断是否有重复元素
                for (; tmp && tmp->val == t; tmp = tmp->next); // 循环结束后 tmp 指向第一个不是当前重复值的节点
                pre->next = tmp; // pre 的 next 成员跨过所有重复元素指向 tmp
            }
            else pre = tmp;
        }
        return fake->next;
    }

# python3
class Solution:
    def deleteDuplicates(self , head ):
        # write code here
        fake = ListNode(0)
        fake.next = head
        pre = fake
        while pre.next:
            t = pre.next.val
            tmp = pre.next
            if tmp.next and t == tmp.next.val:
                while tmp and tmp.val == t:
                    tmp = tmp.next
                pre.next = tmp
            else: pre = tmp
        return fake.next

时间复杂度是 O(n)，空间复杂度是 O(1)

第二种方法（不推荐使用）

先吧所有元素放到数组中，用unique函数去重，最后重建成链表。

    ListNode* deleteDuplicates(ListNode* head) {
        // write code here
        vector<int> res;
        unordered_map<int, int> mp;
        for (; head; head = head->next) {
            int t = head->val;
            if (mp.find(t) == mp.end()) // 没有找到目标元素
                res.push_back(t), mp[t] = 0; // 暂时认为目标元素只会出现一次，mp 中标记出现了该元素
            else if (res[res.size() - 1] == t) res.pop_back(); // 发现目标元素不止出现了一次，如果 res 的结尾依然还有这个重复元素，要将它弹出
        }
        ListNode* fake = new ListNode(0), *pre = fake;
        for (int u : res) pre->next = new ListNode(u), pre = pre->next; // 通过一个循环重建链表
        return fake->next;
    }

时间复杂度是 O(n)，因为使用到了哈希表所以空间复杂度是 O(n)