当前位置：首页 > article >正文

【每日一题】2015考研数据结构 - 求不重复的链表元素

article 2024/11/9 5:36:03

在单链表中存储了 m 个整数，每个节点由两部分组成：[data][link]，其中 data 是整数，且满足 |data| < n（n 为正整数）。
现要求设计一个高效的算法来处理链表中 data 绝对值相等的节点，只保留首次出现的节点，删除其余绝对值相等的节点。

例如，对于以下链表：

1 -> 2 -> -2 -> 3 -> null

经过处理后，得到的链表为：

1 -> 2 -> 3 -> null

解题思路

本题的关键在于高效去重，即在链表中保留首次出现的数值对应的节点，而删除其他绝对值相等的节点。可以借助 哈希表（unordered_set） 来记录已经出现过的节点绝对值。这样，我们可以在遍历链表的同时，实时判断是否存在绝对值重复的节点。

如果你不知道什么是set与实践复杂度的话可参考以下文章

C++ 新手指南：如何使用 set 和 unordered_set
【数据结构】时间复杂度和空间复杂度是什么？

具体思路如下：

从链表头开始遍历，使用一个哈希表 sets 来记录出现过的节点绝对值。
如果当前节点的绝对值没有出现在 sets 中，则将该节点的绝对值插入 sets，并继续遍历。
如果当前节点的绝对值已经出现在 sets 中，说明该节点为重复节点，删除该节点并更新链表结构。
最后得到一个不含重复绝对值节点的链表。

代码实现

数据结构定义

首先定义链表节点的数据结构：

struct Node {
    int value;       // 节点的数值
    Node* next;      // 指向下一个节点的指针
};

算法实现

按照上述思路，以下是完整的 C++ 代码实现：

#include "bits/stdc++.h"

using namespace std;

// 链表节点结构
struct Node {
    int value;
    Node* next;
}; 

// 去除链表中绝对值相同的节点，仅保留首次出现的节点
void search(Node* node) {
    unordered_set<int> sets;  // 用于存储出现过的节点绝对值
    Node* prev = node;        // 记录上一个节点

    while(node != nullptr) {
        // 判断当前节点的绝对值是否在哈希集合中
        if(sets.find(abs(node->value)) == sets.end()) {
            sets.insert(abs(node->value));  // 插入当前节点的绝对值
            prev = node;                    // 更新前驱节点
            node = node->next;              // 移动到下一个节点
        } else {
            // 如果绝对值已存在，删除当前节点
            prev->next = node->next;
            Node* n = node;
            node = node->next;
            free(n);  // 释放删除的节点
        }
    }   
}

测试代码

测试代码如下，构建了一个示例链表并调用 search 函数对其进行去重操作：

int main() {
    Node* head = new Node{1, new Node{2, new Node{-2, new Node{3, nullptr}}}};
    
    Node* cur = head;
    cout << "原链表: ";
    while(cur != nullptr) {
        cout << cur->value << " "; 
        cur = cur->next;
    }
    cout << endl;
    
    search(head); 
    
    cur = head;
    cout << "去重后的链表: ";
    while(cur != nullptr) {
        cout << cur->value << " "; 
        cur = cur->next;
    }
    cout << endl;
    
    return 0;
}

代码讲解

数据结构定义：定义 Node 结构体，包含一个 value 和一个 next 指针，分别表示节点的数值和下一个节点的地址。
去重逻辑：
- 利用哈希集合 sets 来存储已访问的绝对值。在遍历过程中，检查 sets 中是否存在当前节点的绝对值。
- 如果不存在，则将绝对值加入集合并继续遍历。
- 如果存在，则说明当前节点重复，通过调整前驱节点 prev 的指针，跳过该节点并释放其内存。
时间复杂度：由于哈希表的插入、查找操作平均复杂度为 O(1)，因此整体算法的时间复杂度为 O(m)，其中 m 是链表的节点个数。
空间复杂度：由于使用了一个哈希集合来记录绝对值，最坏情况下需要 O(m) 的空间。