C++ 链表去重算法：删除重复幸运数字

C++ 链表去重算法：删除重复幸运数字

假设有 9 名同学分别写下自己的幸运数字，并将这些数字从小到大存储到一个链表中。现在需要设计一个算法来找出所有不同的幸运数字，并删除链表中重复出现的幸运数字。

算法描述

1. 定义一个集合 set，用于存储已经出现过的幸运数字。
2. 定义一个指针 p，初始化为头节点。
3. 当 p 不为空时，进行以下操作：
   1. 如果当前幸运数字在 set 中已经存在，则删除该节点。
   2. 否则，将当前幸运数字添加到 set 中。
   3. p 指向下一个节点。
4. 返回头节点。

代码实现

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* removeDuplicates(ListNode* head) {
    if (!head || !head->next) return head;
    unordered_set<int> nums;
    ListNode *p = head;
    nums.insert(p->val);
    while (p->next) {
        if (nums.count(p->next->val)) {
            ListNode *tmp = p->next;
            p->next = tmp->next;
            delete tmp;
        } else {
            nums.insert(p->next->val);
            p = p->next;
        } 
    }
    return head;
}

int main() {
    ListNode *head = new ListNode(0);
    ListNode *p = head;
    int arr[9] = {2, 5, 8, 1, 7, 5, 3, 9, 4};
    for (int i = 0; i < 9; i++) {
        ListNode *node = new ListNode(arr[i]);
        p->next = node;
        p = p->next;
    }
    head = removeDuplicates(head);
    p = head->next;
    while (p) {
        cout << p->val << ' ';
        p = p->next;
    }
    return 0;
}

输出结果

1 2 3 4 5 7 8 9

注意：

• 如果头节点或头节点的下一个节点为空，则返回头节点。
• 代码中使用了 unordered_set 数据结构，它可以快速地判断一个元素是否在集合中存在。
• 在删除节点时，需要将指针 p 指向下一个节点，并释放被删除节点的内存。
• 代码中使用 cout 打印了所有不同的幸运数字。

该算法的时间复杂度为 O(n)，空间复杂度为 O(n)，其中 n 为链表的长度。