跳转至

ci0201.移除重复结点*

题目描述*

编写代码，移除未排序链表中的重复结点。保留最开始出现的结点。

示例*

输入：[1, 2, 3, 3, 2, 1]

输出：[1, 2, 3]

输入：[1, 1, 1, 1, 2]

输出：[1, 2]

提示*

  • 链表长度在[0, 20000]范围内。
  • 链表元素在[0, 20000]范围内。

进阶*

如果不得使用临时缓冲区，该怎么解决？

代码*

使用哈希表或每次遍历后面所有的。

class Solution {
public:
    ListNode* removeDuplicateNodes(ListNode* head) {
        if(head == nullptr || head->next == nullptr) {
            return head;
        }
        unordered_set<int> hash;
        auto pre = head;
        hash.insert(pre->val);
        while(pre != nullptr && pre->next != nullptr) {
            if(hash.count(pre->next->val)) {
                auto del = pre->next;
                pre->next = del->next;
                delete del;
            }else {
                hash.insert(pre->next->val);
                // 检测到重复不要往前走
                pre = pre->next;
            }
        }
        return head;
    }
};

class Solution {
public:
    ListNode* removeDuplicateNodes(ListNode* head) {
        if(head == nullptr || head->next == nullptr) {
            return head;
        }
        auto pre = head;
        while(pre != nullptr) {
            auto cur = pre;
            while(cur != nullptr && cur->next != nullptr) {
                if(cur->next->val == pre->val) {
                    auto del = cur->next;
                    cur->next = del->next;
                    delete del;
                    del = nullptr;
                }else {
                    cur = cur->next;
                }
            }
            pre = pre->next;
        }
        return head;
    }
};
最后更新: July 23, 2022