题目描述

一个单链表中有 m 个结点，每个结点上的元素的绝对值不超过 n。

现在，对于链表中元素的绝对值相等的结点，仅保留第一次出现的结点而删除其余绝对值相等的结点。

请输出筛选后的新链表。

例如，单链表 21 -> -15 -> -15 -> -7 -> 15，在进行筛选和删除后，变为 21 -> -15 -> -7。

输入样例：
输入：21->-15->-15->-7->15

输出：21->-15->-7
数据范围
1≤m≤1000,
1≤n≤10000

算法

遍历链表的时候，用一个数组标记是否已经出现过该元素。出现就在对应的位置true，否则false；

时间复杂度

O(m)

参考文献

y总

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* filterList(ListNode* head) {
        /*因为题目中链表结点大于等于1，所以不需要判空*/
        //标志数组，标志一个元素是否已经出现过
        bool st[10001] = {};
        //第一个头结点一定会留下，设置true
        st[abs(head->val)] = true;
        //开始从头结点进行遍历，每次判断是否有下一个结点
        for(auto p = head ; p -> next;){
            //下一个结点的值（取绝对值，因为在判断的时候也是从绝对值判断是否删除）
            int x = abs(p->next->val);
            //下一个结点值在数组中已经出现过,删除
            if(st[x]){
                //先保存下一个结点
                auto q = p->next;
                //指向下下个结点
                p->next = q->next;
                //这个时候就可以删除下一个结点了
                delete q;

            }else{//没有出现在数组中，这个点保留
                //p继续遍历下一个位置
                p = p->next;
                //最后标记一下存在该数
                st[x] = true;
            }
        }
        //最后返回头结点
        return head;

    }
};