题目描述

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

样例

示例1:
 输入：[1, 2, 3, 3, 2, 1]
 输出：[1, 2, 3]
示例2:
 输入：[1, 1, 1, 1, 2]
 输出：[1, 2]
提示：
链表长度在[0, 20000]范围内。
链表元素在[0, 20000]范围内。
进阶：
如果不得使用临时缓冲区，该怎么解决？

算法1

(哈希) $O(n)$

重复元素不加，加哈希查不到的元素

时间复杂度 O(n) 空间O(n)

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeDuplicateNodes(ListNode* head) {
        ListNode* pre = new ListNode(-1,head),*cur = head;
        map<int,int> m;
        vector<int> res;
        while(cur)
        {
            if(!m.count(cur->val)){
                m[cur->val] = 1;
                res.push_back(cur->val);
            }
            cur = cur->next;
        }
        ListNode *myhead = new ListNode(-1),*t = myhead;
        for(int i = 0 ; i < res.size();i++)
        {
            ListNode *node = new ListNode(res[i]);
            myhead->next = node;
            node->next = NULL;
            myhead = node;
        }
        return t->next;
    }
};

算法2

(冒泡) $O(n^2)$

遇到重复元素就跳向下一个节点 时间复杂度 O(n^2) 空间o(1)

while(p)
{
    q = p;
    while (q.next != null) 
    {
        if (q->next.val == p.val)q->next = q->next->next;
        else q = q->next;
    }
    p->next = p->next;
}
（没考虑细节，大致是这样的）