[AcWing]3756. 筛选链表

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

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

请输出筛选后的新链表。

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

输入样例：

1
2
3
输入：21->-15->-15->-7->15

输出：21->-15->-7

数据范围

1 < m < 1000,
1 < n < 10000

算法思想

如果要筛选掉重复的元素，那么必须要有记录每个数字是否出现过的bool st[N]。

而且链表中的第1个元素一定是没出现过的，可以直接标记st为true。

image-20240508204615900

对于p和q，删除点有讲究，如果是删除q，那么成本小得多。

所以q就作为被检查节点

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * 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) {
        // 标记该数字是否已经出现过了
        bool st[10010] = {};
        
        // 第1个元素一定没有出现过
        st[ abs(head -> val) ] = true;
        
        // 当前没重复元素的最后一个节点的地址
        ListNode * p = head;
        // 当前被检查的节点存在
        while(p -> next){
            // 当前正在被检查的节点
            ListNode * q = p -> next;
            
            if(st[abs(q -> val)]){
                // 如果出现过了，删除
                p -> next = q -> next;
                delete q;
            }else{
                // 如果没有出现过
                st[abs(q -> val)] = true;
                p = p -> next;
            }
        }
        
        return head;
    }
};