程序员代码面试指南 2.13：删除无序链表中值重复出现的节点

解法一：哈希

1、思路

遍历链表的过程中，将元素的值存入哈希表内，遇到相同值的节点跳过即可；
时间复杂度 $O(N)$ ，空间复杂度 $O(N)$ 。

list_node * remove_rep(list_node * head)
{
    if (head == nullptr || head->next == nullptr) return head;

    unordered_set<int> set;
    auto pre = head, cur = head->next;

    set.insert(head->val);              //头结点不会被删除，先存入哈希表中
    while (cur != nullptr)
    {
        if (set.find(cur->val) != set.end())
        {
            pre->next = cur->next;      //跳过当前节点
        }
        else
        {
            set.insert(cur->val);
            pre = cur;
        }

        cur = cur->next;
    }

    return head;
}

解法二：选择排序法

1、思路

类似选择排序的过程，对于每个节点，检查后面链表中是否有相同值的节点；
时间复杂度 $O(N^2)$ ，空间复杂度 $O(1)$ 。该方法会TLE。

list_node * remove_rep(list_node * head)
{
    list_node *cur = head, *pre = nullptr, *next = nullptr;

    while (cur != nullptr)      //对每一个cur节点，删除链表后半部分中所有与之相同的节点
    {
        pre = cur, next = cur->next;
        while (next != nullptr)
        {
            if (cur->val == next->val)
            {
                pre->next = next->next;
            }
            else
            {
                pre = next;
            }

            next = next->next;
        }

        cur = cur->next;
    }

    return head;
}