每日科普 · 2026-09-27 周日
考研 408 × 求职面试
知识点 · 数据结构 · 进阶
单链表的就地逆置与有序合并
单链表只能从头往后走，因此“就地逆置”就是不改结点数据、不新建结点，只把每个结点的 next 指针掉头。常用三指针法：prev 指向已逆置部分的头，cur 指向当前待处理结点；先用 nxt 保存 cur->next，防止断链，再让 cur->next=prev，随后 prev=cur、cur=nxt。遍历结束 prev 就是新头。空表或单结点无需特殊处理，循环自然返回原头/NULL。
“有序合并”通常指两个升序链表合成一个升序链表。为保持 O(1) 额外空间，应复用原结点，用虚拟头结点和 tail 尾指针：比较两表当前结点值，把较小者接到 tail 后，并移动该表指针；某表先空后，把另一表剩余段整体接上。整个过程只改 next，不 new 新结点，时间 O(m+n)，空间 O(1)。
易错点：逆置时忘记保存后继导致丢链；合并时比较后未移动 tail 或剩余段未接；对带头结点链表要区分头结点和首元结点。掌握这两种指针操作，是链表题的基础。
每日一题 · 数据结构
单链表的就地逆置与有序合并
选择题：关于单链表的就地逆置与两个升序链表的就地合并，下列说法正确的是（ ）。
A. 就地逆置必须新建 n 个结点，空间复杂度 O(n)
B. 两个升序链表合并时，应把较小结点不断插到结果链表头部
C. 就地逆置可用 prev、cur、nxt 三指针完成，时间复杂度 O(n)、空间复杂度 O(1)
D. 有序合并必须复制结点，不能修改原链表的 next 指针
解析
选 C。就地逆置通过先保存 cur->next，再令 cur->next=prev，并同步移动三指针完成，不新建结点，时间 O(n)、空间 O(1)。A、D 错在需要新建/复制；B 错在升序合并应使用尾插法，用虚拟头结点和 tail，依次接入较小结点，最后整体接上未空链表的剩余部分，时间 O(m+n)、空间 O(1)。
面试小贴士 · 数据结构
单链表的就地逆置与有序合并
面试常要求手写逆置或合并，并追问 O(1) 空间与边界。答时先讲三指针/虚拟头尾插，再补空表、单结点、剩余段处理。易错点：丢后继、成环、忘记移动 tail、混淆头结点与首元结点。
代码实现 · C
代码示例
#include <stdio.h>
typedef struct Node { int val; struct Node *next; } Node;
/* 就地逆置 */
Node* reverse(Node* head) {
Node *prev = NULL, *cur = head;
while (cur) {
Node *nxt = cur->next;
cur->next = prev;
prev = cur;
cur = nxt;
}
return prev;
}
/* 合并两个升序链表，复用原结点 */
Node* merge(Node* a, Node* b) {
Node dummy;
Node* tail = &dummy;
dummy.next = NULL;
while (a && b) {
if (a->val <= b->val) { tail->next = a; a = a->next; }
else { tail->next = b; b = b->next; }
tail = tail->next;
}
tail->next = a ? a : b;
return dummy.next;
}