目录
我们先明确问题是什么
你现在有一个链表，例如：
head → [10 | * ] → [25 | * ] → [38 | * ] → [NULL]
你想查找某个“值”（value），例如 25。
我们要回答：
这个值在链表中有没有？
如果有，它在哪个节点？
如果没有，返回什么？
第一步：思考搜索的本质是什么？
搜索的本质是：
依次访问链表中的每个节点，判断当前节点是否是目标值。
由于链表不像数组那样有下标，也不能用二分法（链表不能随机访问），我们只能从头走到尾。
这引出两个核心限制：
链表只能按顺序访问（顺着 next 指针跳）
查找必须从第一个节点开始，直到找到或走到 NULL
举个例子：我们想查找目标值 25，链表是：
head → [10] → [25] → [38] → NULL
我们访问过程是：
访问 head → data = 10，不等于 25
跳到下一个 → data = 25，找到了！
结束搜索
第二步：从数据结构角度推导搜索流程
我们有节点结构如下：
struct Node {
int data;
struct Node* next;
};
你已经有一个链表头指针：
struct Node* head;
搜索步骤：
从
head开始判断
head->data是否等于目标值如果不是，就跳到
head->next重复这个过程，直到：
找到：返回找到的节点
或者遇到 NULL：表示没找到
✅ 我们可以写成 while 循环
struct Node* temp = head;
while (temp != NULL) {
if (temp->data == key) {
// 找到了
}
temp = temp->next;
}
如何设计函数接口？
最基础的设计是：
struct Node* search(struct Node* head, int key);
输入：
链表头指针
head要查找的整数值
key
输出：
如果找到了，返回指向该节点的指针
如果找不到，返回 NULL
背后逻辑总结
| 问题 | 答案（第一性） |
|---|---|
| 为什么不能用下标？ | 链表不支持随机访问，只能靠指针跳转 |
| 为什么要从头到尾遍历？ | 因为链表没有索引，也不能跳跃访问 |
| 为什么返回指针？ | 因为节点不在数组里，不能返回下标，只能返回地址 |
| 为什么要判断 temp != NULL？ | 如果跳到 NULL，表示已经到达链表尾部 |
完整代码
#include <stdio.h>
#include <stdlib.h>
// 节点结构
struct Node {
int data;
struct Node* next;
};
// 查找函数：返回包含 key 的节点指针，找不到返回 NULL
struct Node* search(struct Node* head, int key) {
struct Node* temp = head;
while (temp != NULL) {
if (temp->data == key) {
return temp;
}
temp = temp->next;
}
return NULL;
}
int main() {
// 构建链表：10 → 25 → 38
struct Node* head = (struct Node*) malloc(sizeof(struct Node));
struct Node* second = (struct Node*) malloc(sizeof(struct Node));
struct Node* third = (struct Node*) malloc(sizeof(struct Node));
head->data = 10; head->next = second;
second->data = 25; second->next = third;
third->data = 38; third->next = NULL;
// 测试查找
int key = 25;
struct Node* result = search(head, key);
if (result != NULL) {
printf("Found %d at node address %p\n", key, result);
} else {
printf("%d not found in the list.\n", key);
}
// 释放内存
free(head);
free(second);
free(third);
return 0;
}
用递归来写查找
如何把链表查找从循环形式转化为递归（recursion）形式？
本质逻辑是：
依次从
head开始往下走，每次判断当前节点是不是目标如果是就返回指针
否则继续查下一节点
现在我们问一个本质问题：
每一次查找，其实都是：“看当前节点是不是目标；如果不是，就在剩下的链表中继续查找”
❗这是一种自相似结构（self-similar structure）：
原问题：在链表中查找 key
子问题：在
head->next链表中查找 key
这种“自己包含自己的结构”是递归的本质特征，所以，我们可以用递归来写查找！
递归必须包含两个核心成分：
1️⃣ 递归终止条件（base case）
我们必须规定：
如果链表为空：
head == NULL→ 说明没找到 → return NULL如果当前节点是目标：
head->data == key→ 找到了 → return head
2️⃣ 递归调用（reduction step）
如果当前节点不是目标，且链表未结束：
就在 剩下的链表 中继续找：
return search(head->next, key);
完整递归函数
struct Node* search(struct Node* head, int key) {
if (head == NULL)
return NULL; // 空链表，找不到
if (head->data == key)
return head; // 找到目标
return search(head->next, key); // 在剩下的链表中找
}
链表查找的优化
在标准单链表中：
我们为了查找一个值，只能：
从
head开始，一步步走最坏情况下访问 n 次（O(n)）
但是现实中：
某些数据被频繁查找，例如：
最近访问过的网页
最近用过的文件
那我们有没有方法让“常查找的元素”更快被找到？
我们能不能把常用的值移到靠前的位置？
答案是：可以。
于是诞生了两种经典的启发式（heuristic）查找优化策略：
| 名称 | 核心思想 |
|---|---|
| transposition | 每次找到元素后，把它和前一个元素交换 |
| move-to-head | 每次找到元素后，把它移到表头 |
同样的思路也适用于数组：数据结构：数组：线性查找（Linear Search）-CSDN博客
换位法（transposition）
每当我们在链表中成功找到一个节点后，就把它和它的“前一个节点”交换位置。
举例：现在有链表：
head → [a] → [b] → [c] → [d] → NULL
你查找的是 c
普通查找就是找到它就完了，什么也不变。
换位法查找找到 c 后，把它和前一个 b 交换位置：
head → [a] → [c] → [b] → [d] → NULL
下次如果你又查 c，它更靠前了！
❓为什么这样做？
因为我们认为：
被查到的值，很可能会再次被查找
换位法是一种局部提升，通过一点点移动常用元素向前靠，让以后更快被访问。
我们现在来实现 transposition 搜索
首先，我们要解决一个问题：
单链表中不能“反向走”，那我们怎么知道“当前节点的前一个节点”是谁？
答：我们在查找过程中必须保存两个指针：
struct Node* prev = NULL;
struct Node* curr = head;
curr：当前正在判断的节点prev：curr 前一个节点，用来交换
🔁 每一步：
判断
curr->data == key如果不是，往下走一格：
prev = curr;
curr = curr->next;
如果找到了 key，怎么办？
我们就要把 curr 和 prev 的位置交换。
假设：
prev → [b] → [c] → curr->next → ...
要变成：
prev → [c] → [b] → curr->next → ...
//等价于
prev->next = curr->next;
curr->next = prev;
但还不够 —— 谁来指向 curr？你还要修改“prev 的前一个节点”的指针！
✅ 所以我们还需要一个：prePrev（prev 的前一个）
struct Node* prePrev = NULL;
struct Node* prev = NULL;
struct Node* curr = head;
🔍 具体交换步骤
在链表中，“交换节点”不是交换它们的数据内容（那是数组思维），而是重新安排它们之间的指针关系。
原状态：
prePrev → prev → curr → after
prev->next == curr
curr->next == after
第一步：让 prev 跳过 curr，直接指向 after
prev->next = curr->next; // 现在 prev → after
此时链表变成：
prePrev → prev curr → after
↘
→ after
curr 暂时还没有连上前面的节点
第二步：让 curr->next 指向 prev
curr->next = prev;
prePrev → prev curr
↘ ↗
→ after
但注意，此时 prePrev → prev 还是旧的指向，我们还没有把 curr 插入前面。
第三步：修复前一个前驱的指针
我们要让：
prePrev->next = curr;
prePrev → curr → prev → after
如果 prePrev == NULL 呢？
那就说明 prev 是头节点，要特别处理，把 head 本身更新为 curr：
*head = curr;
最终操作顺序
prev->next = curr->next;
curr->next = prev;
if (prePrev != NULL)
prePrev->next = curr;
else
*head = curr;
| 步骤 | 本质意义 |
|---|---|
| 保存前驱指针 | 单链表不能反向走，必须显式保存 |
| 找到目标后交换节点 | 用指针操作完成 curr 和 prev 的调换 |
| 更频繁访问的节点向前移动 | 增加将来访问速度 |
完整过程总结图解
初始状态：
prePrev → prev → curr → after
第一步：
prev->next = curr->next;
prePrev → prev curr → after
↘
→ after
第二步：
curr->next = prev;
prePrev → prev ← curr
↘
→ after
第三步：
prePrev->next = curr;
prePrev → curr → prev → after
完整代码
#include <stdio.h>
#include <stdlib.h>
// 节点结构
struct Node {
int data;
struct Node* next;
};
// 打印链表
void printList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("%d → ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
// 使用换位法查找 key
struct Node* searchTransposition(struct Node** head, int key) {
if (*head == NULL) return NULL;
struct Node* prePrev = NULL;
struct Node* prev = NULL;
struct Node* curr = *head;
while (curr != NULL) {
if (curr->data == key) {
// 找到了，和前一个节点交换
if (prev == NULL) {
// 第一个节点，不需要换位
return curr;
}
// 一般情况：交换 prev 和 curr
prev->next = curr->next;
curr->next = prev;
if (prePrev == NULL) {
// prev 是头节点
*head = curr;
} else {
prePrev->next = curr;
}
return curr;
}
// 没找到，继续往后走
prePrev = prev;
prev = curr;
curr = curr->next;
}
return NULL; // 没找到
}
// 构建链表
struct Node* buildList() {
struct Node* a = (struct Node*) malloc(sizeof(struct Node));
struct Node* b = (struct Node*) malloc(sizeof(struct Node));
struct Node* c = (struct Node*) malloc(sizeof(struct Node));
struct Node* d = (struct Node*) malloc(sizeof(struct Node));
a->data = 10; a->next = b;
b->data = 20; b->next = c;
c->data = 30; c->next = d;
d->data = 40; d->next = NULL;
return a; // head
}
int main() {
struct Node* head = buildList();
printf("Original list:\n");
printList(head);
int key = 30;
searchTransposition(&head, key);
printf("After searching %d (transposition):\n", key);
printList(head);
return 0;
}
移到表头（Move-to-Head）
从第一性出发，讲解 Move-to-Head（移到表头） 策略：每次查找到一个节点之后，将其移到链表最前面。
第一性推导：为什么要这么做？
在实际应用中，有些元素被访问的频率非常高。我们希望这些“常被访问的节点”靠前，这样下次能更快地被找到。
Move-to-Head 的核心思想：
一旦某个节点被找到，就直接把它移动到表头，这样下次查找就最快（O(1)）
head → [10] → [20] → [30] → [40] → NULL
你查找 30，找到了它。操作后：
head → [30] → [10] → [20] → [40] → NULL
30被提到了表头原来它后面的节点顺序没有改变
原来在它前面的节点整体往后推
为什么这样做是合法的？
链表中节点之间是通过指针连接的
你只需要修改三条指针：
断开原位置上的连接
将目标节点插入表头
更新
head指针
🔍 具体实现步骤
假设你已经找到了节点 curr，它不是第一个节点
你在查找过程中保存了两个指针：
struct Node* prev = ...; // curr 的前一个节点
struct Node* curr = ...; // 当前查找到的节点
当前链表结构为：
head → ... → prev → curr → curr->next → ...
Step 1: 断开 curr 原来的位置
我们要让 prev 跳过 curr，指向 curr->next：
prev->next = curr->next;
此时链表是：
head → ... → prev → curr->next
↘
curr
Step 2: 把 curr 插入表头
curr->next = head;
Step 3: 更新 head 指针
*head = curr;
现在链表是：
head → curr → 原来的头 → ...
完成 ✅
❗边界情况：如果 curr 本来就是头节点呢？
if (curr == *head)
return curr;
什么都不做，直接返回
代码实现
// 在链表中查找 key，并将其移到表头
struct Node* searchMoveToHead(struct Node** head, int key) {
if (*head == NULL) return NULL;
// 如果第一个节点就是目标
if ((*head)->data == key)
return *head;
struct Node* prev = *head;
struct Node* curr = prev->next;
while (curr != NULL) {
if (curr->data == key) {
// Step 1: 从原位置断开
prev->next = curr->next;
// Step 2: 插到头部
curr->next = *head;
*head = curr;
return curr;
}
// 向后移动
prev = curr;
curr = curr->next;
}
return NULL; // 没找到
}
| 步骤 | 操作代码 | 含义 |
|---|---|---|
| 断开 curr | prev->next = curr->next |
把 curr 从原位置拿出来 |
| 插入表头 | curr->next = head |
把 curr 指向原头节点 |
| 更新头指针 | *head = curr |
把 curr 变成新的头节点 |
两种方式对比
| 特性 | Move-to-Head | Transposition |
|---|---|---|
| 移动距离 | 一次到表头 | 每次前移一步 |
| 修改影响 | 对链表影响大 | 对链表影响小 |
| 查找性能提升速度 | 快 | 慢 |
| 适合数据访问模式 | 极端热点（少数项频繁访问） | 中等热点（多项中等频率） |