第3章 链表算法

旧版讲义 · 校订增强 · 专题阅读 · 保留代码与校订注 · 与版本锁一致

第3章 链表算法

基本口径与安全改链：先认清头结点，再动 next

“带头结点”和“头指针”到底差在哪里？

何时用：所有单链表算法落笔前；题干说“带头结点”时尤其要先统一口径。

思路步骤：

1. 头指针 head 指向头结点；头结点不存有效数据，首个数据结点是 head->next。
2. 空表的判定是 head!=NULL 且 head->next==NULL。
3. 需要修改首个数据结点时，让 pre 从 head 开始，可统一普通位置与表首位置。
4. 若题目是不带头结点链表，函数往往要接收二级指针或返回新表头，不能直接照搬。

伪代码/关键模板：

typedef struct ACNode {
    int data;
    struct ACNode *next;
} ACNode;

复杂度：口径本身无复杂度；头结点让表首插删保持 O(1) 且少一个特判。

易错边界：不要把头结点算入表长或倒数第 k 个；head==NULL 表示连头结点都不存在，与空表不是同一状态；本章默认“带头结点”。

回源 · PDF 第 72 页 · b_72_11；PDF 第 72 页 · b_72_13；PDF 第 72 页 · b_72_15；PDF 第 72 页 · b_72_16

遍历带头结点单链表，起点和终止条件怎样写？

何时用：统计长度、查值、打印、求和，以及绝大多数链表算法的基础扫描。

思路步骤：

1. p=head->next，从首个数据结点开始。
2. 在 p!=NULL 时处理 p->data。
3. 每轮末尾令 p=p->next。
4. 若需要删除或插入，另设 pre，不能只保留当前 p。

伪代码/关键模板：

static int ac_list_length(const ACNode *head) {
    int n = 0;
    if (head == NULL) return 0;
    for (const ACNode *p = head->next; p != NULL; p = p->next) ++n;
    return n;
}

复杂度：时间 O(n)，额外空间 O(1)。

易错边界：从 head 开始会把头结点误计；循环内漏写推进会死循环；链表若有环，普通遍历不会终止，应先判环或以长度限制。

回源 · PDF 第 75 页 · b_75_0；PDF 第 75 页 · b_75_1；PDF 第 75 页 · b_75_6；PDF 第 75 页 · b_75_10

删除当前结点时，为什么必须先保存 next？

何时用：扫描过程中删除满足条件的结点，尤其是一轮内可能连续删除多个结点时。

思路步骤：

1. 维护 pre 指向当前 p 的前驱。
2. 命中删除条件时先保存 next=p->next。
3. 令 pre->next=next，再释放 p，最后 p=next；此时 pre 不动。
4. 未删除时才同时推进 pre=p、p=p->next。

伪代码/关键模板：

static void ac_delete_value(ACNode *head, int value) {
    if (head == NULL) return;
    ACNode *pre = head;
    ACNode *p = head->next;
    while (p != NULL) {
        if (p->data == value) {
            ACNode *next = p->next;
            pre->next = next;
            free(p);
            p = next;
        } else {
            pre = p;
            p = p->next;
        }
    }
}

复杂度：时间 O(n)，额外空间 O(1)。

易错边界：free(p) 后绝不能再读 p->next；连续命中时 pre 不前进。新版增强（不判旧版考试写法错误）：若题目只考链表逻辑且允许省略内存回收，可按评分要求书写；本卡按完整 C 所有权口径保存后继、修链后 free。共享后缀等场景则不能擅自释放。

回源 · PDF 第 73 页 · b_73_4；PDF 第 73 页 · b_73_7；PDF 第 73 页 · b_73_10；PDF 第 73 页 · b_73_12

在 pre 后插入结点，怎样避免丢掉原后继？

何时用：已知插入位置前驱 pre，把现有结点 node 插到其后。

思路步骤：

1. 保存原后继 old_next=pre->next。
2. 令 node->next=old_next。
3. 再令 pre->next=node。
4. 若 node 原本属于另一条链，先从原链安全摘下；不能让同一结点同时被两条独立链拥有。

伪代码/关键模板：

static int ac_insert_after(ACNode *pre, ACNode *node) {
    if (pre == NULL || node == NULL) return 0;
    ACNode *old_next = pre->next;
    node->next = old_next;
    pre->next = node;
    return 1;
}

复杂度：已知 pre 时，时间 O(1)，额外空间 O(1)。

易错边界：若先写 pre->next=node，再从 pre->next 取原后继就已丢失；插入自身会成环；“在 p 前插入”需要先找前驱或采用数据交换技巧，不能假装有前向指针。

回源 · PDF 第 73 页 · b_73_15；PDF 第 73 页 · b_73_17；PDF 第 73 页 · b_73_19；PDF 第 74 页 · b_74_9

头插与尾插分别保留或逆转什么顺序？

何时用：用已有结点建表、把一段链表逆置，或归并时决定结果顺序。

思路步骤：

1. 头插：每个新结点插在头结点后，输入顺序会反转。
2. 尾插：维护 tail 指向当前尾结点，新结点接到 tail 后，输入顺序保留。
3. 尾插后要更新 tail；插入已有结点时先保存其原 next。
4. 最终尾结点 next 必须为 NULL。

伪代码/关键模板：

static void ac_push_front(ACNode *head, ACNode *node) {
    if (head == NULL || node == NULL) return;
    node->next = head->next;
    head->next = node;
}

static void ac_push_back(ACNode *head, ACNode **tail, ACNode *node) {
    if (head == NULL || tail == NULL || *tail == NULL || node == NULL) return;
    node->next = NULL;
    (*tail)->next = node;
    *tail = node;
}

复杂度：有头结点/尾指针时单次插入均为 O(1)；额外空间 O(1)。

易错边界：尾插若每次从头找尾会退化为 O(n²)；头插天然逆序，不适合要求保序的建表；空表时 tail 初值应为 head。

回源 · PDF 第 74 页 · b_74_1；PDF 第 74 页 · b_74_2；PDF 第 74 页 · b_74_3；PDF 第 74 页 · b_74_6；PDF 第 74 页 · b_74_7

有序归并与快慢指针：利用单向结构而非随机访问

两条升序链表怎样原地归并并复用结点？

何时用：两个带头结点的升序链表合并，要求不新建数据结点。

思路步骤：

1. p、q 分别指向两表首个数据结点，tail 指向结果尾部。
2. 比较 p、q，把较小结点接到 tail 后并推进对应指针。
3. 每接一个结点都推进 tail。
4. 某一表结束后，直接接上另一表剩余链。

伪代码/关键模板：

static ACNode *ac_merge_lists(ACNode *h1, ACNode *h2) {
    if (h1 == NULL || h2 == NULL) return h1;
    ACNode *p = h1->next, *q = h2->next, *tail = h1;
    while (p != NULL && q != NULL) {
        if (p->data <= q->data) {
            tail->next = p;
            p = p->next;
        } else {
            tail->next = q;
            q = q->next;
        }
        tail = tail->next;
    }
    tail->next = p != NULL ? p : q;
    h2->next = NULL;
    return h1;
}

复杂度：时间 O(m+n)，额外空间 O(1)。

易错边界：复用结点后第二个头结点不再拥有原数据链；若两表共享结点，普通归并会破坏结构；相等元素是否保留两份由题意决定。

回源 · PDF 第 78 页 · b_78_0；PDF 第 78 页 · b_78_4；PDF 第 78 页 · b_78_6；PDF 第 79 页 · b_79_2

快慢指针判环与找中点，循环条件为何不同？

何时用：判环、寻找链表中点、把链表分成前后两半。

思路步骤：

1. 判环：slow 每次一步、fast 每次两步；能相遇则有环。
2. 找中点：链表必须无环；让 slow、fast 都从首个数据结点出发。
3. 当 fast 后面不足两步时停止，slow 是前半段末结点。
4. 切分时先保存 slow->next，再令 slow->next=NULL。

伪代码/关键模板：

static int ac_has_cycle(const ACNode *head) {
    const ACNode *slow = head, *fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return 1;
    }
    return 0;
}

static ACNode *ac_first_half_end(ACNode *head) {
    if (head == NULL || head->next == NULL) return head;
    ACNode *slow = head->next, *fast = head->next;
    while (fast->next != NULL && fast->next->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

复杂度：时间 O(n)，额外空间 O(1)。

易错边界：求中点前必须排除环；访问 fast->next->next 前先保证 fast->next 非空；偶数长度时本模板返回前半段最后一个结点。

回源 · PDF 第 79 页 · b_79_5；PDF 第 79 页 · b_79_6；PDF 第 79 页 · b_79_7；PDF 第 80 页 · b_80_0

前后指针保持固定间隔，怎样抽象“倒数第 k 个”？

何时用：单链表倒数第 k 个、删除倒数第 k 个，或让两个指针之间保持固定距离。

思路步骤：

1. lead、trail 都从头结点出发。
2. lead 先走 k 个数据边；若不足 k 个，问题无解。
3. 之后两者同步移动，保持相差 k 个结点。
4. lead 到尾结点时，trail->next 就是倒数第 k 个数据结点。

伪代码/关键模板：

static const ACNode *ac_kth_from_end(const ACNode *head, int k) {
    if (head == NULL || k <= 0) return NULL;
    const ACNode *lead = head, *trail = head;
    for (int i = 0; i < k; ++i) {
        if (lead->next == NULL) return NULL;
        lead = lead->next;
    }
    while (lead->next != NULL) {
        lead = lead->next;
        trail = trail->next;
    }
    return trail->next;
}

复杂度：一次线性扫描，时间 O(n)，额外空间 O(1)。

易错边界：k 必须为正；头结点不计入名次；先行指针的起点与停止条件必须成套，否则会差一位。

回源 · PDF 第 80 页 · b_80_3；PDF 第 80 页 · b_80_6；PDF 第 80 页 · b_80_7；PDF 第 80 页 · b_80_8

逆置与结构变换：每次改链前都保存后继

原地逆置单链表，三指针各自负责什么？

何时用：整表逆置、只逆置后半段、回文判断、2019 重排等。

思路步骤：

1. prev 保存已逆置部分的表头，cur 指向待处理结点。
2. 先保存 next=cur->next。
3. 改向 cur->next=prev，把 cur 纳入已逆置部分。
4. prev=cur、cur=next；结束后把头结点 next 指向 prev。

伪代码/关键模板：

static ACNode *ac_reverse_chain(ACNode *first) {
    ACNode *prev = NULL, *cur = first;
    while (cur != NULL) {
        ACNode *next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

static void ac_reverse_after_head(ACNode *head) {
    if (head != NULL) head->next = ac_reverse_chain(head->next);
}

复杂度：时间 O(n)，额外空间 O(1)。

易错边界：改 cur->next 前不保存 next 会丢失余链；空表和单结点表应自然成立；本函数反转数据链，不反转头结点。

回源 · PDF 第 81 页 · b_81_7；PDF 第 82 页 · b_82_0；PDF 第 82 页 · b_82_1；PDF 第 82 页 · b_82_2；PDF 第 82 页 · b_82_7

回文链表怎样做到 O(n)、O(1)，还不破坏原表？

何时用：判断带头结点单链表是否回文，且要求常数额外空间。

思路步骤：

1. 快慢指针找到前半段末结点。
2. 原地逆置后半段。
3. 从表首与逆置后半段同步比较；后半段比较完即可。
4. 再逆置一次并接回，恢复输入结构。新版增强（不判旧解错误）：若题设只要求判断且允许改变链表，比较后不恢复也能完成题意；本卡给出不破坏输入结构的版本。

伪代码/关键模板：

static int ac_is_palindrome_restore(ACNode *head) {
    if (head == NULL) return 0;
    ACNode *first_end = ac_first_half_end(head);
    ACNode *second = ac_reverse_chain(first_end->next);
    int same = 1;
    for (ACNode *p = head->next, *q = second; q != NULL; p = p->next, q = q->next) {
        if (p->data != q->data) {
            same = 0;
            break;
        }
    }
    first_end->next = ac_reverse_chain(second);
    return same;
}

复杂度：时间 O(n)，额外空间 O(1)。

易错边界：比较失败也必须恢复链表；奇数长度时中间结点无需与自己比较；若链表可能有环，应先判环。

回源 · PDF 第 90 页 · b_90_0；PDF 第 90 页 · b_90_1；PDF 第 91 页 · b_91_1；PDF 第 91 页 · b_91_2；PDF 第 91 页 · b_91_4；PDF 第 91 页 · b_91_5

两条升序链表怎样不排序就合成降序链表？

何时用：两条升序链表原地合并，结果要求降序，且允许复用原结点。

思路步骤：

1. 像升序归并一样，每次摘下两表当前较小结点。
2. 但不尾插，而是把摘下结点头插到结果头结点之后。
3. 摘取顺序从小到大，头插后整体自然从大到小。
4. 一表耗尽后继续逐个摘取另一表并头插。

伪代码/关键模板：

static ACNode *ac_merge_descending(ACNode *h1, ACNode *h2) {
    if (h1 == NULL || h2 == NULL) return h1;
    ACNode *p = h1->next, *q = h2->next;
    h1->next = NULL;
    while (p != NULL || q != NULL) {
        ACNode *node;
        if (q == NULL || (p != NULL && p->data <= q->data)) {
            node = p;
            p = p->next;
        } else {
            node = q;
            q = q->next;
        }
        node->next = h1->next;
        h1->next = node;
    }
    h2->next = NULL;
    return h1;
}

复杂度：时间 O(m+n)，额外空间 O(1)。

易错边界：摘下 node 后先保存原后继；若要求去重，相等分支还需删除/跳过一个结点；两个原头结点的归属要说明清楚。

回源 · PDF 第 88 页 · b_88_0；PDF 第 88 页 · b_88_1；PDF 第 89 页 · b_89_2；PDF 第 89 页 · b_89_3；PDF 第 89 页 · b_89_5；PDF 第 89 页 · b_89_6

链表综合方法：比较、摘取、复用结点

稀疏多项式相加，怎样把“归并”扩展到同指数消项？

何时用：两个带头结点多项式链表按指数降序，要求结果仍降序并尽量复用原结点。

思路步骤：

1. p、q 指向两表当前项，pre 指向 p 的前驱。
2. p 指数更大：保留 p，推进 p/pre。
3. q 指数更大：把 q 从 L2 摘下并插到 pre 与 p 之间。
4. 指数相等：系数相加；若为 0，同时删除该指数项；否则保留合并项。
5. L2 若有剩余，直接接到 L1 尾部。

伪代码/关键模板：

typedef struct ACPolyNode {
    long long coef;
    int exp;
    struct ACPolyNode *next;
} ACPolyNode;

static ACPolyNode *ac_add_polynomial(ACPolyNode *h1, ACPolyNode *h2) {
    if (h1 == NULL || h2 == NULL) return h1;
    ACPolyNode *pre = h1, *p = h1->next, *q = h2->next;
    while (p != NULL && q != NULL) {
        if (p->exp > q->exp) {
            pre = p;
            p = p->next;
        } else if (p->exp < q->exp) {
            ACPolyNode *qnext = q->next;
            q->next = p;
            pre->next = q;
            pre = q;
            q = qnext;
        } else {
            p->coef += q->coef;
            ACPolyNode *qnext = q->next;
            free(q);
            q = qnext;
            if (p->coef == 0) {
                ACPolyNode *dead = p;
                p = p->next;
                pre->next = p;
                free(dead);
            } else {
                pre = p;
                p = p->next;
            }
        }
    }
    if (q != NULL) pre->next = q;
    h2->next = NULL;
    return h1;
}

复杂度：时间 O(m+n)，额外空间 O(1)。

易错边界：比较的是指数而不是系数；相同指数相加为 0 时必须同时修链和释放；摘取 q 前先保存 q->next；函数会消费 L2 的数据结点。

回源 · PDF 第 92 页 · b_92_0；PDF 第 92 页 · b_92_1；PDF 第 93 页 · b_93_2；PDF 第 93 页 · b_93_3；PDF 第 93 页 · b_93_4；PDF 第 94 页 · b_94_1

两个升序链表求交集，怎样原地保留 L1 中的公共结点？

何时用：两个无重复升序链表求值交集，要求结果写回 L1，额外空间 O(1)。

思路步骤：

1. p、q 分别扫描 L1、L2，tail 指向 L1 中最后一个已保留结点。
2. p->datadata 时，该 p 不可能再匹配，删除 p。
3. p->data>q->data 时，推进 q。
4. 相等时保留 p，推进 p、q 与 tail。
5. 任一链结束后，删除 L1 中剩余未匹配结点。

伪代码/关键模板：

static void ac_free_chain(ACNode *p) {
    while (p != NULL) {
        ACNode *next = p->next;
        free(p);
        p = next;
    }
}

static ACNode *ac_sorted_intersection(ACNode *h1, const ACNode *h2) {
    if (h1 == NULL || h2 == NULL) return h1;
    ACNode *p = h1->next, *tail = h1;
    const ACNode *q = h2->next;
    while (p != NULL && q != NULL) {
        if (p->data < q->data) {
            ACNode *dead = p;
            p = p->next;
            tail->next = p;
            free(dead);
        } else if (p->data > q->data) {
            q = q->next;
        } else {
            tail = p;
            p = p->next;
            q = q->next;
        }
    }
    ac_free_chain(p);
    tail->next = NULL;
    return h1;
}

复杂度：时间 O(m+n)，额外空间 O(1)。

易错边界：这里求的是“值交集”，与共享后缀的“地址相同”不是一题；删除 L1 结点前保存后继；若结点被外部共享，不能直接 free。

回源 · PDF 第 94 页 · b_94_2；PDF 第 94 页 · b_94_3；PDF 第 95 页 · b_95_7；PDF 第 95 页 · b_95_8；PDF 第 96 页 · b_96_0；PDF 第 96 页 · b_96_8

统考真题路线：把公共模板写成完整答案

2009 倒数第 k 个，怎样按真题要求返回成功状态和值？

何时用：带头结点单链表只给头指针，不改变链表，查找倒数第 k 个并通过返回值表示成败。

思路步骤：

1. 复用固定间隔模板，让 lead 先走 k 步。
2. 不足 k 个数据结点立即失败。
3. lead 与 trail 同步走到末端。
4. 把 trail->next 的 data 写入输出参数，返回 1；失败返回 0。

伪代码/关键模板：

static int ac_kth_value(const ACNode *head, int k, int *out) {
    if (out == NULL) return 0;
    const ACNode *node = ac_kth_from_end(head, k);
    if (node == NULL) return 0;
    *out = node->data;
    return 1;
}

复杂度：时间 O(n)，额外空间 O(1)，且链表结构不变。

易错边界：k≤0、空表、长度不足 k 都失败；不要把头结点算入 k；输出参数只有成功时才写入。

回源 · PDF 第 96 页 · b_96_10；PDF 第 96 页 · b_96_13；PDF 第 98 页 · b_98_8；PDF 第 98 页 · b_98_9；PDF 第 98 页 · b_98_11；PDF 第 99 页 · b_99_1

2012 公共后缀，为什么比较地址而不是字符值？

何时用：两条单链表可能共享一段实际存储结点，求共同后缀的起始结点。

思路步骤：

1. 分别求两链数据结点长度 len1、len2。
2. 较长链先走长度差，使两个指针到表尾的剩余距离相同。
3. 两指针同步后移，第一次 p==q 的结点就是公共后缀起点。
4. 同值但不同地址不算共享；若始终不相等则返回 NULL。

伪代码/关键模板：

static const ACNode *ac_common_suffix_start(const ACNode *h1, const ACNode *h2) {
    int n1 = ac_list_length(h1), n2 = ac_list_length(h2);
    const ACNode *p = h1 == NULL ? NULL : h1->next;
    const ACNode *q = h2 == NULL ? NULL : h2->next;
    while (n1 > n2) {
        p = p->next;
        --n1;
    }
    while (n2 > n1) {
        q = q->next;
        --n2;
    }
    while (p != NULL && q != NULL && p != q) {
        p = p->next;
        q = q->next;
    }
    return p == q ? p : NULL;
}

复杂度：时间 O(m+n)，额外空间 O(1)。

易错边界：核心判定是 p==q，不是 p->data==q->data；共享结点以后 next 链天然相同；共享结构不能由某一条链单独释放。

回源 · PDF 第 99 页 · b_99_2；PDF 第 99 页 · b_99_3；PDF 第 99 页 · b_99_12；PDF 第 100 页 · b_100_7；PDF 第 100 页 · b_100_8；PDF 第 101 页 · b_101_0；PDF 第 101 页 · b_101_1

2015 按绝对值去重，散列表值域和删除动作怎样同时写对？

何时用：链表含 m 个整数，且 |data|≤n，只保留每种绝对值第一次出现的结点。

思路步骤：

1. seen[0..n] 记录某绝对值是否出现，空间由值域 n 决定。
2. pre 指向 p 的前驱；首次出现就标记并同步前进。
3. 已出现时保存 p->next，修正 pre->next，释放 p，再从保存处继续。
4. 用 long long 计算绝对值，避免对 INT_MIN 直接调用 abs。

伪代码/关键模板：

static int ac_abs_dedup(ACNode *head, int n) {
    if (head == NULL || n < 0) return 0;
    for (ACNode *p = head->next; p != NULL; p = p->next) {
        long long v = p->data;
        if (v < 0) v = -v;
        if (v > n) return 0;
    }
    unsigned char *seen = calloc((size_t)n + 1U, sizeof(*seen));
    if (seen == NULL) return 0;
    ACNode *pre = head, *p = head->next;
    while (p != NULL) {
        long long v = p->data;
        if (v < 0) v = -v;
        if (!seen[(size_t)v]) {
            seen[(size_t)v] = 1;
            pre = p;
            p = p->next;
        } else {
            ACNode *next = p->next;
            pre->next = next;
            free(p);
            p = next;
        }
    }
    free(seen);
    return 1;
}

复杂度：时间 O(m+n)（含 seen 初始化；题目常简写 O(m+n)），空间 O(n)。若 n=O(m)，也可按题目口径写线性空间。

易错边界：值域包含 0 和 n，所以数组长 n+1；删除时 pre 不移动；空间复杂度由 n 而非链长 m 决定；分配失败不能继续访问 seen。

回源 · PDF 第 101 页 · b_101_2；PDF 第 101 页 · b_101_3；PDF 第 102 页 · b_102_2；PDF 第 103 页 · b_103_3；PDF 第 103 页 · b_103_4；PDF 第 103 页 · b_103_8；PDF 第 103 页 · b_103_9

2019 重排为 a1,an,a2,an-1…，三段结构变换怎样闭环？

何时用：带头结点单链表要求原地重排为首、尾、次首、次尾……，时间 O(n)、额外空间 O(1)。

思路步骤：

1. 快慢指针找到前半段末结点 first_end。
2. 从 first_end->next 切开，并把后半段原地逆置。
3. p 指向前半段，q 指向逆置后的后半段。
4. 每轮先保存 pnext、qnext，再接 p->q->pnext，之后同步推进。
5. 后半段耗尽时结束；奇数长度的中间结点已留在前半段末尾。

伪代码/关键模板：

static void ac_reorder_2019(ACNode *head) {
    if (head == NULL || head->next == NULL || head->next->next == NULL) return;
    ACNode *first_end = ac_first_half_end(head);
    ACNode *second = ac_reverse_chain(first_end->next);
    first_end->next = NULL;
    ACNode *p = head->next, *q = second;
    while (q != NULL) {
        ACNode *pnext = p->next;
        ACNode *qnext = q->next;
        p->next = q;
        q->next = pnext;
        p = pnext;
        q = qnext;
    }
}

复杂度：找中点、逆置、交叉合并各 O(n)，总时间 O(n)，额外空间 O(1)。

易错边界：新版补充/校订：旧版 p105 只展示到新建后半段头结点，完整实现跨页截断；本卡给出校订完成版，证据仍锚定 p104–105 的题意、步骤和部分代码。切链、逆置、交织每次都要先保存 next；无需 malloc 新头结点。

回源 · PDF 第 104 页 · b_104_0；PDF 第 104 页 · b_104_3；PDF 第 104 页 · b_104_5；PDF 第 105 页 · b_105_4；PDF 第 105 页 · b_105_5；PDF 第 105 页 · b_105_6；PDF 第 105 页 · b_105_9；PDF 第 105 页 · b_105_10；PDF 第 105 页 · b_105_11