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

链表污染或节点劫持

news 2026/7/24 3:30:26

一、场景模拟：

1. 当前我有两个结构体，一个用来存储节点，另一个用来存储符合条件内容的节点。

typedef struct TempNode { book_n *book_ptr; // 指向原始图书节点的指针 struct TempNode *next; } TempNode; // 临时链表头 typedef struct { TempNode *head; int count; } TempList; // 函数 TempList* filter_by_one_condition(TempList *input_list, SearchCondition *search); // 参数1：TempList *input_list; // 输入链表，要遍历的链表 // 参数2：SearchCondition *search; // 查找条件 // TempList *new_list; // 返回的符合条件的新链表

2. 假设输入的链表 input_list 中有三本书，分别是 A、B、C，其中符合条件的书是 A 和 C，我们需要把 A 和 C 放到 new_list 节点中。

二、代码逻辑：

1. 遍历 input_list 节点，找到符合的节点 A、C。

2. 创建 new_list 节点，将节点 A 和 C 分别插入到 new_list 节点中。

3. 返回新创建的 new_list 节点。

// 错误写法 // curr_temp 是遍历节点 if (is_match) { // 符合条件 if (new_list->head == NULL) { new_list->head = curr_temp; // 直接把输入链表的节点 A 拿过来当头 tail = curr_temp; } else { tail->next = curr_temp; // 【致命】修改了 A 的 next 指针，让它指向 C tail = curr_temp; } }

三、步骤模拟

第一步：处理节点 A（匹配）：

1.curr_temp指向A。

2.new_list为空。

3.new_list->head = A。

4.tail = A。

此时内存状态：

输入链表视角：A -> B -> C（还没变，因为没动A->next）

结果链表视角：Head -> A

第二步：处理节点 B（不匹配）：

1.curr_temp指向B。

2.is_match为假，跳过，不做任何操作。

3. 循环继续，curr_temp变为C。

输入链表：A -> B -> C

结果链表：Head -> A（Tail 还是 A）

第三步：处理节点 C（匹配）—— 灾难发生时刻

1.curr_temp指向C。

2.is_match为真。

3. 此时tail是A。

此时会把 A 的 next 指针，强行改成指向 C！

如果没有其他指针指向 B，B 就变成了"孤儿节点"（内存泄漏）。

如果你后续还要遍历输入链表（比如curr_temp = curr_temp->next），你会直接从 A 跳到 C，永远漏掉 B 之后的所有节点（如果 B 后面还有 D、E... 它们也全丢了）。

此时的内存状态：

[ Node A ] ──next──→ [ Node C ] +----------+ +----------+ | data: A | | data: C | | next: |──┐ | next: |──→ NULL (假设 C 原来是尾节点) +----------+ │ +----------+ └──────→ (原本指向 B，现在被强制改向 C) [ Node B ] <── 🕸️ 孤儿节点！没人指向它了，内存泄漏！ +----------+ | data: B | | next: |──→ ... +----------+

第四步：潜在的崩溃（如果 C 不是最后一个）

假设输入链表是A -> B -> C -> D。C 匹配，D 不匹配。

1、执行tail->next = C（即A->next = C）。

2、tail更新为C。

3、循环结束。

结果链表：Head -> A -> C。

但是在输入链表中，C->next指向D。

因为你没有创建新节点，也没有把C->next设为NULL，结果链表的尾部依然挂着 D！

当你遍历结果链表打印时：

打印 A。
顺着A->next找到 C。
打印 C。
顺着C->next找到D。
打印 D！（哪怕 D 根本不匹配条件！）

结果污染：
结果链表里混入了不匹配的节点，因为它们的next指针还连着原链表的后续部分。

正确做法：

/* 输入链表（完好无损）：[A] -> [B] -> [C] -> [D] 结果链表（独立新建）：[New_A] -> [New_C] | | v v （指向A） （指向C） New_A->next 指向 New_C New_C->next 是 NULL 原链表 A->next 依然指向 B，不受影响。 */ // 代码部分 while (curr_temp != NULL) { // ... 判断 is_match ... if (is_match) { // 【关键步骤】为当前匹配的书，申请一块新的内存空间 TempNode *new_node = (TempNode *)malloc(sizeof(TempNode)); // 填充这个新节点 new_node-&gt;book_ptr = curr_temp-&gt;book_ptr; // 指向真正的书 new_node-&gt;next = NULL; // 初始化 next // 链接到结果链表 if (new_list-&gt;head == NULL) { new_list-&gt;head = new_node; tail = new_node; } else { tail-&gt;next = new_node; tail = new_node; } new_list-&gt;count++; } curr_temp = curr_temp-&gt;next; // 继续检查下一本输入链表中的书 }