6/26刷题

1.移除重复节点
编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
示例1:
输入：[1, 2, 3, 3, 2, 1]
输出：[1, 2, 3]
示例2:
输入：[1, 1, 1, 1, 2]
输出：[1, 2]
提示：
链表长度在[0, 20000]范围内。
链表元素在[0, 20000]范围内。
进阶：
如果不得使用临时缓冲区，该怎么解决？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicate-node-lcci
思路一：哈希表

class Solution {
public:
    ListNode* removeDuplicateNodes(ListNode* head) {
        if (head == nullptr) {
            return head;
        }
        unordered_set<int> occurred = {head->val};//记录出现过的节点
        ListNode* pos = head;
        // 枚举前驱节点
        while (pos->next != nullptr) {
            // 当前待删除节点
            ListNode* cur = pos->next;
            if (!occurred.count(cur->val)) {
                occurred.insert(cur->val);
                pos = pos->next;//如果未出现过，就插入哈希表，然后后移
            } else {
                pos->next = pos->next->next;//出现过就跳过此数
            }
        }
        pos->next = nullptr;
        return head;
    }
};

思路二：双重循环

class Solution {
public:
    ListNode* removeDuplicateNodes(ListNode* head) {
        ListNode* ob = head;
        while (ob != nullptr) {
            ListNode* oc = ob;
            while (oc->next != nullptr) {
                if (oc->next->val == ob->val) {
                    oc->next = oc->next->next;
                } else {
                    oc = oc->next;
                }
            }
            ob = ob->next;
        }
        return head;
    }
};