1. 这题到底在考什么链串替换背后的核心知识点PTA 上这道链串替换算法题表面上是让你写一个字符串替换的链表实现实际上考的是三件事的叠加串的基本概念、链表操作的熟练度、还有边界情况的处理能力。很多同学看到“链串”两个字就开始发怵觉得它是个冷门概念实际上它就是把字符串用链表来存仅此而已。但恰恰因为这个“仅此而已”反而让它的操作比顺序串数组存串要绕一些。先帮大家串一下知识背景。数据结构里的“串”就是字符串常见的存储方式有两种一种是顺序存储也就是用一个定长数组或者动态数组把字符连续存放C 语言里的 char[] 就是典型代表另一种就是这里要说的链式存储每个结点里装一个字符或者多个字符结点之间用指针串起来像一串糖葫芦。顺序串的好处是按下标随机访问特别快但插入和删除要移动大量元素代价很高链串恰好反过来插入删除只要改指针非常灵活但要按下标访问某个字符就得从头一个个遍历过去。替换算法放在链串上来做其实比顺序串更有讨论价值。顺序串做替换最麻烦的是长度变化。比如把“hello”里的“ll”换成“world”替换后新串比原串长你得先把数组里的元素从后往前搬移腾出空间再填入新内容如果替换后变短了你还得把后面的元素往前挪再把尾部多余的空间截掉。整个过程对下标的把控非常容易出错一个 1 一个 -1 就能让你调试半天。而链串替换的核心逻辑完全是另一套找到目标子串的起始位置和结束位置把这一段从链子上“摘下来”然后把新串的结点链“接上去”。整个过程只涉及指针的重新指向不涉及任何元素的物理搬移。这也是链串在算法设计领域被反复拿来当教学案例的原因——它让你真正理解链表操作的本质改指针就是增删遍历就是访问。PTA 之所以把这题编号放在“串的算法设计”系列里说明它的定位不是单纯考链表基本功而是考你能不能把串的模式匹配思想迁移到链式结构上。模式匹配是串这一章的绝对核心在顺序串里你写暴力匹配有几个 for 循环就搞定但到了链串里你没有下标可用你只有 next 指针。你必须自己想清楚怎么从一个结点出发顺着 next 走若干步去逐字符比较比较失败后主串的指针应该回退到哪个位置重新开始。这个“回退”的过程恰恰是链串替换最容易出错的地方。另一个容易被忽略的考点是内存管理。顺序串替换不需要管内存分配但链串替换要被替换掉的那段结点你不能让它们变成悬空结点得一个个 free 掉新建的替换串得根据 V 串的长度动态申请结点如果目标子串在链表中出现多次你还要决定是只替换第一次出现还是全部替换。PTA 的题目在这里通常会给出明确要求比如“将链串 s 中所有与 t 相等的子串替换为 v”那么你的代码就要在一个循环里反复查找、替换直到链尾而不是匹配一次就结束。我见过不少同学的版本思路是对的但最终提交就是过不了评测点。问题大多出在找到了要替换的位置但是把 pre 指针指错了或者替换完了之后p 指针没有移动到替换串的尾部导致后面还有相同子串时漏掉再或者删除了结点但没释放内存虽然功能上没错但严格来说不算“算法的正确实现”。这篇文章我就按照 PTA 真题的思路把链串替换算法从结构定义、核心思路、完整代码到调试心得完整走一遍希望能帮你把这题吃透也帮你把链串这一类题目的套路彻底拿住。2. 链串的设计选择为什么有“块链”和“单字符链”两种形态在写替换算法之前先得把链串的存储结构定下来。这一步非常重要因为不同的结点设计会直接影响你替换算法的复杂度和代码写法。链串结点最常见的两种设计一是单字符结点链串也就是每个结点只存一个字符data 字段是一个 char二是块链串也就是每个结点里存一个长度为 m 的字符数组比如char data[4]结点与结点之间用 next 指针连接。这两种设计各有来头不是随意发明的。单字符链串的优点在于逻辑最简单每个结点对应一个字符你要找第 k 个字符就从表头走 k 次 next你要删除一段子串只要数清楚这段子串有几个字符对应的就是多少个结点删除时把这些结点逐个摘下来释放就行。缺点非常明显存储密度低。每个结点除了数据还要占一个指针域在 64 位系统上指针占 8 字节而 char 只占 1 字节也就是说一个结点约 88.9% 的空间都被指针本身消耗掉了。存一个 100 字符的字符串实际要 100 个结点光指针就占 800 字节。这在教学场景里无所谓但在工程场景里是不可接受的浪费。块链串就是为了解决存储密度问题而生的。一个结点里放 4 个或 8 个字符指针域还是那 8 字节存储密度一下子就上去了。比如结点内放 4 个字符一个结点的有效载荷是 4 字节总空间是 4812 字节存储密度约 33%比单字符结点强了不少。但块链串有个麻烦操作不够均匀。你查找字符时得先定位到某个结点再判断字符在结点内 data 数组的第几个位置你在块内做插入删除时还可能要挪动块内的元素这就把数组操作引入了链表操作中代码复杂度明显上升。回到 PTA 这道题题目本身一般不会强制指定你用哪种链串结构但你要根据替换操作的特点来选。替换算法要做三件事匹配目标子串、删除原串中的目标段、插入新串。如果你用单字符链串这三件事都极其直观匹配就是逐结点比较删除就是摘除 n 个结点插入就是逐个结点复制新串的字符。如果你用块链串匹配和删除都要处理“块内偏移”的问题新串插进去之后还可能拆散原有的块结构处理起来非常繁琐很容易绕晕。所以我的建议很明确这道题老老实实选单字符链串结点。不是为了炫技而是为了在有限的时间里把核心算法逻辑写清楚。PTA 评测只关注你的运行结果和内存使用是否合理单字符链串虽然存储密度低但对于长度不大的测试数据完全可以接受。等你把这个算法彻底想明白将来真要在工程里优化存储再去改块链串也不迟。结点的 C 语言定义如下typedef struct LNode { char data; // 当前结点存储的字符 struct LNode *next; // 指向下一个结点的指针 } LinkStrNode;这种结构在 PTA 题目里经常还会配合头结点来使用。头结点是一个特殊的哑结点它的 data 域不存有效字符只作为操作的统一入口存在。为什么要加头结点因为带头结点的链表在“删除第一个结点”或者“在头部插入新结点”时不需要单独修改头指针的值统一用head-next来操作就可以了代码逻辑更加一致。对于替换算法来说匹配起点可能就在第一个字符比如 s 串是“hello”t 串是“h”替换后新的头结点位置会改变。如果没有头结点你就得用一个二级指针或者返回值来更新头指针麻烦得很。带头结点之后无论链子怎么变函数只需要操作head-next最后返回head即可。构造链串的过程也很简单给定一个普通 C 字符串char str[]你从头到尾遍历它为每个字符创建一个新结点串到链尾。这里有一个小细节C 字符串末尾有\0\0要不要放进链串里我的建议是不放。原因有二一是 PTA 里打印链串时你看的是有效字符如果有\0结点遍历输出时反而要多一层判断二是替换算法中你操作的仅仅是有效字符区间单独把一个终止符作为结点放进去没有任何算法上的好处反而增加了删除和插入时的字符计数负担。所以链串的末尾结点 next 指向 NULL 即可这就等同于字符串的“结束标志”。如果你要写辅助函数我建议至少准备这几个createLinkString(char *s)用普通字符串创建链串displayLinkString(LinkStrNode *head)遍历打印链串linkStringLength(LinkStrNode *head)计算链串长度。这三个函数是后续实现替换算法的地基也是你在 PTA 调试时最依赖的工具。别嫌它们简单后面查 bug 的时候你就知道有多香了。3. 替换算法的核心思路从“暴力匹配”到“指针重连”现在切入正题链串替换算法到底怎么设计。我先把这题的标准描述复述一遍方便对照设计一个算法将链串 s 中所有与链串 t 相等的子串替换为链串 v。要求在原链串上进行操作不得借助顺序串的辅助空间输出的结果仍为链串。题目要求在原链串上操作这一点非常关键。这意味着你不能偷懒先把链串转成字符数组用顺序串的思路跑一遍替换再转回链串。这种“曲线救国”的写法虽然结果对但不符合题目的空间要求也没有体现链式结构的操作特征在考试或者面试里不会被认可。那么正确思路是什么样子我把它拆成三块来看查找、删除、插入。3.1 查找在链串中定位目标子串查找这一步本质上就是字符串模式匹配中的暴力匹配算法在链表上的变形。主串 s 用指针 p 遍历子串 t 用指针 q 遍历。每到一个新的起点 p 时我把 p 暂存到一个临时指针start中然后让 q 从 t 的头结点后第一个有效结点开始与 start 同步往后走逐字符比较。如果一路比较到 q 走到 NULL说明 t 串全部匹配成功那么从 start 到当前停下来的位置之间的这段结点就是我们要替换的目标段。如果中途某个字符不比配说明从 start 开始的这段不可能是目标子串于是 p 从 start 的下一个结点开始进入下一轮匹配。这个“从 start 的下一个结点重新开始”的操作在链串里对应的是p start-next。这里要特别提醒不要图省事写成p p-next。因为当比较失败时p 已经不在 start 的位置了它可能已经跑到 start 后面好几个结点去了。如果你直接 p p-next等于把起点跳过了漏掉了一种可能。举个例子s 是“aaa”t 是“aa”。第一个起点是 s 的第一个结点匹配成功后如果你直接把 p 移到被匹配段的尾部那下一轮匹配就会从第三个结点开始结果第二个起点匹配不到了最后只替换了一处。所以正确做法是每次匹配开始前记录 start不管匹配成功还是失败下一轮 p 都要从 start-next 开始。这样才是最朴素的、不重不漏的暴力匹配。3.2 删除把目标段从链子上摘下来找到目标段后我们要把它删除。这里的“删除”包含两层含义第一层是从链表中摘除让目标段前后结点直接相连第二层是释放被摘除结点的内存空间防止内存泄漏。两层缺一不可。有些同学只改了指针没有 free 结点这在小型测试用例里可能不会被发现但一旦涉及大量数据或者反复替换内存泄漏会越来越严重在某些评测环境下会因为内存超限而直接扣分。摘除操作的关键是记住目标段前一个位置的结点。我把它记为pre指针。在匹配过程中start 是目标段的第一个结点pre 是 start 的前一个结点。当我们确定要从 pre-next 一直删到 tail目标段的最后一个结点时先执行pre-next tail-next这一步就把目标段从整个链表中解开了目标段后面的那部分tail 之后的结点现在成了 pre 的下一个结点。接下来要回收目标段的内存。用一个临时指针temp从 start 开始逐个向后移动每移动一个结点就 free 一个。注意在 free 之前要先把下一步的地址存下来否则 free 之后你就找不到 next 了。代码模式如下LinkStrNode *temp start; while (temp ! tail-next) { LinkStrNode *nextNode temp-next; free(temp); temp nextNode; }有个细节很多人都没意识到tail 怎么获取在匹配过程中我们的 q 指向的是 t 串从头开始往后走的结点当 q 走到 NULL 时start 到某个位置的结点是匹配成功的。我们需要记录这个匹配的终点。我建议在匹配时维护两个指针start和end。start 指向匹配段的起点end 指向匹配段的最后一个结点。每次 start 和 q 同步比较成功一个字符end 就更新为 start 当前所在的位置。匹配结束后end 自然就是目标段的最后一个结点。tail 其实就是 end 的别名看你怎么命名。3.3 插入把替换串的结点链接上去删除完成之后pre-next 已经指向目标段后面的部分链子上留下了一个“豁口”。接下来我们要把 v 串的所有有效字符结点插入到这个豁口上。插入的做法是从头遍历 v 串每遇到一个有效字符就创建一个新结点然后把新结点依次链接到 pre 后面。这个过程要用三个指针协作一个指针 cur 指向 v 串当前要复制的结点一个指针 newTail 指向新链的最后一个结点初始时和 pre 相同还有一个指针 newNode 指向每次新创建的结点。每创建一个 newNode就让newTail-next newNode然后 newTail 更新为 newNode。这样所有的新结点就串联起来了。循环结束后把newTail-next pre-next也就是让新串的尾结点接上之前豁口后面留下的那部分结点。这样一来新串就完整地嵌入了原链串。千万不要忘了v 串本身是一棵独立的链串你不能直接把它的头结点或者首个结点嫁接到原链串上。因为那样会破坏 v 串本身的结构而且如果题目还要继续使用原 v 串就会出现数据共享导致的意想不到的后果。安全做法永远是创建新结点、逐个复制字符。这也是链表操作的一个基本原则你要“值”而不是要“地址”时就复制结点。3.4 循环与终止处理“所有匹配项”PTA 要求替换所有匹配的子串所以整个查找-删除-插入的过程要放在一个大循环里。大循环的终止条件是主串指针 p 已经遍历到链串末尾p 为 NULL。不过这里有个很有意思的边界问题替换完成之后p 应该指向哪里题目中没有明说但在“替换所有子串”的要求下比较安全的做法是让 p 指向新插入部分的第一个结点然后继续匹配。也就是说插入完成后我们并不跳跃到豁口后面的部分而是从新串的第一个字符开始继续尝试匹配。为什么这样做举个极端的例子s 串是“aa”t 是“a”v 是“aa”。如果你替换第一个“a”后把 p 直接跳到原串的第二个字符那最终结果是“aa”后接原来的“a”变成“aaa”其中前两个“a”其实是新插入的“aa”。这没问题。但如果你要求的是所有原串中的“a”都被替换而新插入的“aa”里也可能出现“a”那这个结果就取决于题目对“所有”的定义——是“原串中所有匹配位置”还是“替换完成后的最终串中所有匹配位置”。通常数据结构教材和 PTA 题目都默认前者即不递归处理新插入的内容避免死循环。像我刚说的 s“aa”、t“a”、v“aa”如果对新插入内容继续匹配那“aa”中间又会出现“a”替换后又变成“aa”……无限递归。所以必须停止对新插入内容的继续匹配。实现上插入完成后让 p 从豁口后面的原串结点开始继续遍历即可。具体到代码里你可以这样处理插入完成后记录nextStart newTail-next这就是豁口之后原串接下来的部分的第一个结点。然后把大循环指针 p 赋值为 nextStart继续下一轮匹配。这是一个非常实用的经验能帮你避开很多诡异的死循环和重复替换问题。4. 完整代码实现从结构到主函数的逐步落地讲了这么多思路是时候给出一个可以直接在 PTA 环境里跑通的完整实现了。我手写了一个版本把前面提到的每个细节都落实在代码里。你拿去提交前建议先照着思路过一遍再决定是否照抄——因为 PTA 的题目描述可能有细微差别比如头结点是否标准、输出格式要求等你需要做对应微调。但核心的替换函数replace部分基本是这个套路。#include stdio.h #include stdlib.h #include string.h typedef struct LNode { char data; struct LNode *next; } LinkStrNode; // 创建链串从普通字符串 str 构造带头结点的链串 LinkStrNode *createLinkString(char *str) { LinkStrNode *head (LinkStrNode *)malloc(sizeof(LinkStrNode)); head-next NULL; LinkStrNode *tail head; for (int i 0; str[i] ! \0; i) { LinkStrNode *node (LinkStrNode *)malloc(sizeof(LinkStrNode)); node-data str[i]; node-next NULL; tail-next node; tail node; } return head; } // 输出链串 void displayLinkString(LinkStrNode *head) { LinkStrNode *p head-next; while (p ! NULL) { putchar(p-data); p p-next; } putchar(\n); } // 计算链串长度 int linkStringLength(LinkStrNode *head) { int len 0; LinkStrNode *p head-next; while (p ! NULL) { len; p p-next; } return len; } // 在链串 s 中将所有与 t 相等的子串替换为 v void replace(LinkStrNode *s, LinkStrNode *t, LinkStrNode *v) { if (s NULL || t NULL || v NULL || t-next NULL) { return; } LinkStrNode *p s-next; // 主串遍历指针 LinkStrNode *pre s; // p 的前驱结点 while (p ! NULL) { LinkStrNode *start p; // 本轮匹配的起点 LinkStrNode *q t-next; // 模式串 t 的遍历指针 LinkStrNode *end NULL; // 匹配段的最后一个有效结点 // 从 start 开始和 q 逐字符比较 LinkStrNode *cur start; while (q ! NULL cur ! NULL) { if (cur-data q-data) { end cur; cur cur-next; q q-next; } else { break; } } // q NULL 表示 t 串完全匹配成功 if (q NULL) { // 1. 摘除 [start, end] 这一段 pre-next end-next; // 2. 释放摘除结点的内存 LinkStrNode *temp start; while (temp ! end-next) { LinkStrNode *nextNode temp-next; free(temp); temp nextNode; } // 3. 将 v 串的结点复制并插入到 pre 后面 LinkStrNode *newTail pre; LinkStrNode *vCur v-next; while (vCur ! NULL) { LinkStrNode *newNode (LinkStrNode *)malloc(sizeof(LinkStrNode)); newNode-data vCur-data; newNode-next NULL; newTail-next newNode; newTail newNode; vCur vCur-next; } // 4. 新串尾部接上原串剩余部分 newTail-next end-next; // 5. 下一轮从原串剩余部分的第一个结点开始继续匹配 p end-next; pre newTail; } else { // 匹配失败p 和 pre 都向前移动一个结点 pre p; p p-next; } } } int main() { char s[100], t[100], v[100]; // 输入 S 串 scanf(%s, s); // 输入 T 串 scanf(%s, t); // 输入 V 串 scanf(%s, v); LinkStrNode *sLink createLinkString(s); LinkStrNode *tLink createLinkString(t); LinkStrNode *vLink createLinkString(v); replace(sLink, tLink, vLink); displayLinkString(sLink); // 释放内存完整的实现还应包括释放 sLink、tLink、vLink 的辅助函数 return 0; }这个版本里有几个地方我想特别解释一下。首先replace函数中t-next NULL的判断是用来处理 t 是空串的情况。空串没有可匹配的内容直接返回即可。否则进入匹配流程q 一开始为空很容易造成空匹配所以提前拦掉。其次pre指针的维护是整个函数最容易写错的地方。匹配失败时pre 应该从 p 的位置挪到 p 的下一个位置但你不能直接把 pre 挪到 cur 停下来的位置因为 cur 可能已经走了好几步了。我代码里的写法是失败时pre 更新为 p当前这一轮匹配的起点然后 p 更新为 p-next。这样就实现了“从匹配起点的下一个结点重新开始”的语义。如果匹配成功pre 要保持指向新插入串的最后一个结点这样才能保证后续的匹配中如果需要再次摘除结点pre 能正确指向要被删的那段的前驱。我在代码里匹配成功后的最后写了pre newTail;这个语句很多人会漏掉漏掉的后果是下一轮匹配如果又遇到匹配成功删除结点时 pre 还指向旧位置链子就断错了。再次关于删除和插入的顺序我的做法是先摘除、再释放、再插入、最后接尾部。这个顺序很关键。如果你先插入再释放那么 free 目标段结点时新插入的结点的 next 会指向已经被释放的内存形成悬垂指针。而我的顺序中插入完成后直接把 newTail-next 指向 end-next因为 end-next 在此之前已经被保存好在第一步摘除时pre-next 已经被改成 end-next但 end-next 这个指针值依然有效它指向原串剩余部分。这就是链表操作的奥妙改变指针指向不等于改变了被指向的东西。还有一个容易埋雷的细节end-next在第一步摘除之后原目标段最后一个结点 end 虽然已经被摘出了链外但它的 next 仍然保留着原串剩余部分的地址所以我在插入完成后能放心引用end-next。这里我用的是它的值不需要 end 这个结点本身还在链上。这就是“摘除”和“释放”之间那一小段时间窗口里的信息保留。5. 踩坑记录与快速定位这些 bug 你真的可能遇到代码给出来了但不代表你照着写就一定一次通过。PTA 的评测点往往在你想不到的边界上等着你。我把这些年批改和自测中常见的错误整理成一份清单每一类我都见过至少三次绝对是高频重灾区。5.1 匹配成功却始终不输出替换结果这种问题多半出在主串指针 p 的推进逻辑上。多数同学的错误版本是这样的匹配失败时让p p-next匹配成功时也让p p-next。表面看没问题但一旦出现“成功匹配后 p 正好指向目标段的最后一个结点”那么 p 的下一轮起点就是目标段后面那个结点没有遗漏。而如果你在匹配成功后发现 p 指向的是 end 而不是 start 的下一个位置就会少匹配一些情况。用“aaa”和“aa”这个经典用例去测试就能立刻暴露问题。最好的检查方法是在每个分支给 p 赋值后手工模拟几个小用例看看 p 是否覆盖了所有可能的起点。5.2 替换后链串出现“断裂”或“环”断裂一般是因为没有把新串的尾结点接回原串剩余部分。环则是因为你在摘除目标段前忘了把 pre-next 断开导致新插入的结点接到了一个仍然指向目标段内部的链子上。这两种 bug 我在调试时最喜欢用“一个长度为 10 的链串输出前 20 个结点”的办法来检查。如果输出超过 10 个字符还在继续那基本就是成环了。如果你写代码时对每个 free 之前的 next 都先保存再操作这类问题会少很多。5.3 内存重复释放当你把目标段摘除后如果连续走到两个匹配位置而第一个位置释放的过程中你错误地把end-next也当成了目标段的一部分给 free 掉了那么第二个位置的 pre 就会指向非法内存。这种问题不容易在结果上看到异常但一旦把代码搬到带内存检测的环境比如 Valgrind 或者 PTA 的严格模式就会报出 “double free” 或 “invalid free”。写这类代码时建议每次 free 一个结点前先明确这个结点是否已经脱离了主链表还要确定它不会被后续操作再次引用。5.4 空串和单字符特殊情况v 是空串时替换操作本质上是删除所有匹配的 t 子串。这个情况要特别小心v 串没有有效结点插入循环一次都不会执行但你还是要把目标段摘除并释放然后把 pre 和 p 的关系正确维护好。如果 v 串的表示是一个只有头结点、next 为 NULL 的链串代码里那个 while (vCur ! NULL) 循环自然跳过newTail 就还是 prenewTail-next end-next 照样把链子接好所以我的代码天然支持空 v 串。这也是为什么我坚持用带头结点的链串结构——空串的处理变得非常自然。5.5 t 等于 v 时怎么办如果 t 和 v 是同一个字符串比如 s“abc”、t“b”、v“b”那这个替换操作应该等于什么也不做。但如果你在代码里每次匹配成功后都执行删除再插入那么你会把原来的“b”结点删掉再新建一个“b”结点。结果虽然一样但白白浪费了时间和空间。更关键的是如果你的删除逻辑里有任何破绽这种“同替换”的情况就会暴露出来。我在实际测试中遇到过学生写的代码在 tv 的情况下把 s 中所有 b 删光了原因就是删除之后 p 的移动位置不对。所以测试用例里务必加上这一条。5.6 连续匹配导致漏替换s“aaaa”t“aa”v“bb”。第一次从第 1 个字符开始匹配成功替换了前两个字符为“bb”剩下原串第 3、4 个字符“aa”。第二次 p 从原串第 3 个字符开始又匹配成功替换为“bb”最后结果是“bbbb”。这个逻辑是正确的。但如果你在第一次匹配成功后把 p 设置为 end-next 之前忘了把 pre 更新为 newTail第二次匹配时 pre 还指向原串第 0 个位置的结点一删除就会把新插入的“bb”后面的一段给误删掉。这就是我前面反复强调 pre 更新必要性的原因。下面是一个排查对照表你可以把它当作“急救手册”来用现象最可能的原因快速检查方法替换后少了一段内容摘除目标段时删多了或 pre 位置错误打印摘除前 pre-next 的值和 end-next 对比替换后输出出现重复字符插入结点的 next 没接回剩余部分打印 newTail-next 是否为 end-next多次替换时漏匹配p 移动的位置跳过了一个可能的起点用 s“aaa”, t“aa” 验证程序运行非常慢但结果正确暴力匹配在长串上的正常表现也可能存在多余循环使用长 1000 的随机串测试估算耗时运行时崩溃访问了已释放结点常见于 end-next 被 free 后仍引用检查释放前是否保存了 end-next死循环 / 输出截断替换后 p 没有向后推进加计数器限制最大循环次数调试6. 链串替换的变式与扩展为什么不建议用“重建法”到这里标准解题思路已经讲完了。但我知道很多同学在接触这类题时脑子里冒出的第一个想法其实是干脆把链串转成字符数组在数组里做替换完事再转回链串。这个方法我称之为“重建法”。它在功能上确实可行尤其在数据量不大的时候还特别容易写对。但我强烈不建议你在 PTA 这道题里用它原因有三层。第一层是题目要求。PTA 的“串的算法设计”系列明确强调链式存储的应用而不只是结果正确。评测时虽然不检查你是否真的“在原链串上操作”数据结构课程的练习目的摆在那里你用顺序串的思路完成链串作业本质上是用数组解决了链表题没有练到该练的能力。第二层是性能。重建法需要遍历链串转数组又要在数组里做可能触发多次元素搬移的替换最后还要遍历数组重新建链。对于长串和多次替换来说这比纯粹的链上操作要多出不少常数开销。虽然在 O 记号下两者的渐进复杂度可能接近但实际常数差异在数据量大时非常明显。第三层是面试场景。很多公司的面试官喜欢拿链表题目当手写代码题链串替换就是很典型的变种。你在白板上写一个重建法面试官一眼就能看出你没有真正理解链表的优势但如果你能写出“匹配-摘除-插入”的版本同时再解释清楚为什么不直接嫁接到 v 串是因为数据共享问题那面试官对你的评价会完全不一样。链串替换本身还能延伸出好几个变式值得你继续想想仅替换第一次出现大循环改成找到第一个匹配后直接 return逻辑上更简单。大小写不敏感匹配比较字符时统一用 tolower 转换即可。交叉匹配处理比如 s 是“ababa”t 是“aba”寻找所有不重叠的匹配结果应该是 1 个而不是 2 个。因为重叠匹配会导致替换结果非常诡异。我代码里每次匹配成功后 p 跳到 end-next天然避开了重叠匹配这是大多数题目默认的语义。替换计数函数加一个计数器返回替换次数这在统计类题目里很实用。块链串版本每个结点存多个字符匹配和删除都需要处理块内偏移。这个变式能帮你彻底理解“物理连续”和“逻辑连续”的差别但代码量会大很多不推荐作为第一轮学习目标。我自己在实际做题时还有几个小小的习惯想分享。第一个习惯是给链串写一个“可视化打印”函数比如printf(s: ); displayLinkString(s)每次替换操作前后都打印一遍肉眼就能看出哪里断链。第二个习惯是准备一组固定的小测试用例包括空串、单字符、完全匹配、部分匹配、多次匹配、t 和 v 等长、v 比 t 长、v 比 t 短这八种情况每次写完代码都跑一遍。这八种情况基本覆盖了所有边界分支能挡住九成以上的低级错误。第三个习惯是每次 free 一个结点之后立刻把它的 next 置为 NULL。虽然这不是必须的但能防止某些情况下二次 free 时误判。如果你在调试时发现替换后的链串少了一段不要急着全面检查代码。先在删除和插入的边界打两个断点第一个在摘除后打印pre-next和pre的关系第二个在插入结束后打印newTail-next。看到这两个指针的状态问题基本就定位了。这种“分段验证”的思路比从头到尾逐行读代码高效得多。链串替换这道题做透了你对“串”这一章的理解绝对会上一个台阶。它看起来只是链表的增删查改但真正动手写一遍你会发现指针的前后关系、内存的申请释放、边界条件的处理每一个环节都在考验你的工程思维。就像厨师切菜菜刀也就那么多用法但切丝、切片、切丁的每一刀都有讲究。链串替换里的每一根指针就是你的刀工。做完这道题再去碰 KMP 算法优化子串匹配你会觉得链表版的匹配逻辑亲切得多——因为 KMP 解决的是“匹配失败后快速回退”的问题而在链串里回退本身就是最昂贵的操作。理解了这个痛点你才算真正入门了字符串算法设计。 PTA链串替换算法详解：链表操作与指针重连核心思路
1. 这题到底在考什么链串替换背后的核心知识点PTA 上这道链串替换算法题表面上是让你写一个字符串替换的链表实现实际上考的是三件事的叠加串的基本概念、链表操作的熟练度、还有边界情况的处理能力。很多同学看到“链串”两个字就开始发怵觉得它是个冷门概念实际上它就是把字符串用链表来存仅此而已。但恰恰因为这个“仅此而已”反而让它的操作比顺序串数组存串要绕一些。先帮大家串一下知识背景。数据结构里的“串”就是字符串常见的存储方式有两种一种是顺序存储也就是用一个定长数组或者动态数组把字符连续存放C 语言里的 char[] 就是典型代表另一种就是这里要说的链式存储每个结点里装一个字符或者多个字符结点之间用指针串起来像一串糖葫芦。顺序串的好处是按下标随机访问特别快但插入和删除要移动大量元素代价很高链串恰好反过来插入删除只要改指针非常灵活但要按下标访问某个字符就得从头一个个遍历过去。替换算法放在链串上来做其实比顺序串更有讨论价值。顺序串做替换最麻烦的是长度变化。比如把“hello”里的“ll”换成“world”替换后新串比原串长你得先把数组里的元素从后往前搬移腾出空间再填入新内容如果替换后变短了你还得把后面的元素往前挪再把尾部多余的空间截掉。整个过程对下标的把控非常容易出错一个 1 一个 -1 就能让你调试半天。而链串替换的核心逻辑完全是另一套找到目标子串的起始位置和结束位置把这一段从链子上“摘下来”然后把新串的结点链“接上去”。整个过程只涉及指针的重新指向不涉及任何元素的物理搬移。这也是链串在算法设计领域被反复拿来当教学案例的原因——它让你真正理解链表操作的本质改指针就是增删遍历就是访问。PTA 之所以把这题编号放在“串的算法设计”系列里说明它的定位不是单纯考链表基本功而是考你能不能把串的模式匹配思想迁移到链式结构上。模式匹配是串这一章的绝对核心在顺序串里你写暴力匹配有几个 for 循环就搞定但到了链串里你没有下标可用你只有 next 指针。你必须自己想清楚怎么从一个结点出发顺着 next 走若干步去逐字符比较比较失败后主串的指针应该回退到哪个位置重新开始。这个“回退”的过程恰恰是链串替换最容易出错的地方。另一个容易被忽略的考点是内存管理。顺序串替换不需要管内存分配但链串替换要被替换掉的那段结点你不能让它们变成悬空结点得一个个 free 掉新建的替换串得根据 V 串的长度动态申请结点如果目标子串在链表中出现多次你还要决定是只替换第一次出现还是全部替换。PTA 的题目在这里通常会给出明确要求比如“将链串 s 中所有与 t 相等的子串替换为 v”那么你的代码就要在一个循环里反复查找、替换直到链尾而不是匹配一次就结束。我见过不少同学的版本思路是对的但最终提交就是过不了评测点。问题大多出在找到了要替换的位置但是把 pre 指针指错了或者替换完了之后p 指针没有移动到替换串的尾部导致后面还有相同子串时漏掉再或者删除了结点但没释放内存虽然功能上没错但严格来说不算“算法的正确实现”。这篇文章我就按照 PTA 真题的思路把链串替换算法从结构定义、核心思路、完整代码到调试心得完整走一遍希望能帮你把这题吃透也帮你把链串这一类题目的套路彻底拿住。2. 链串的设计选择为什么有“块链”和“单字符链”两种形态在写替换算法之前先得把链串的存储结构定下来。这一步非常重要因为不同的结点设计会直接影响你替换算法的复杂度和代码写法。链串结点最常见的两种设计一是单字符结点链串也就是每个结点只存一个字符data 字段是一个 char二是块链串也就是每个结点里存一个长度为 m 的字符数组比如char data[4]结点与结点之间用 next 指针连接。这两种设计各有来头不是随意发明的。单字符链串的优点在于逻辑最简单每个结点对应一个字符你要找第 k 个字符就从表头走 k 次 next你要删除一段子串只要数清楚这段子串有几个字符对应的就是多少个结点删除时把这些结点逐个摘下来释放就行。缺点非常明显存储密度低。每个结点除了数据还要占一个指针域在 64 位系统上指针占 8 字节而 char 只占 1 字节也就是说一个结点约 88.9% 的空间都被指针本身消耗掉了。存一个 100 字符的字符串实际要 100 个结点光指针就占 800 字节。这在教学场景里无所谓但在工程场景里是不可接受的浪费。块链串就是为了解决存储密度问题而生的。一个结点里放 4 个或 8 个字符指针域还是那 8 字节存储密度一下子就上去了。比如结点内放 4 个字符一个结点的有效载荷是 4 字节总空间是 4812 字节存储密度约 33%比单字符结点强了不少。但块链串有个麻烦操作不够均匀。你查找字符时得先定位到某个结点再判断字符在结点内 data 数组的第几个位置你在块内做插入删除时还可能要挪动块内的元素这就把数组操作引入了链表操作中代码复杂度明显上升。回到 PTA 这道题题目本身一般不会强制指定你用哪种链串结构但你要根据替换操作的特点来选。替换算法要做三件事匹配目标子串、删除原串中的目标段、插入新串。如果你用单字符链串这三件事都极其直观匹配就是逐结点比较删除就是摘除 n 个结点插入就是逐个结点复制新串的字符。如果你用块链串匹配和删除都要处理“块内偏移”的问题新串插进去之后还可能拆散原有的块结构处理起来非常繁琐很容易绕晕。所以我的建议很明确这道题老老实实选单字符链串结点。不是为了炫技而是为了在有限的时间里把核心算法逻辑写清楚。PTA 评测只关注你的运行结果和内存使用是否合理单字符链串虽然存储密度低但对于长度不大的测试数据完全可以接受。等你把这个算法彻底想明白将来真要在工程里优化存储再去改块链串也不迟。结点的 C 语言定义如下typedef struct LNode { char data; // 当前结点存储的字符 struct LNode *next; // 指向下一个结点的指针 } LinkStrNode;这种结构在 PTA 题目里经常还会配合头结点来使用。头结点是一个特殊的哑结点它的 data 域不存有效字符只作为操作的统一入口存在。为什么要加头结点因为带头结点的链表在“删除第一个结点”或者“在头部插入新结点”时不需要单独修改头指针的值统一用head-next来操作就可以了代码逻辑更加一致。对于替换算法来说匹配起点可能就在第一个字符比如 s 串是“hello”t 串是“h”替换后新的头结点位置会改变。如果没有头结点你就得用一个二级指针或者返回值来更新头指针麻烦得很。带头结点之后无论链子怎么变函数只需要操作head-next最后返回head即可。构造链串的过程也很简单给定一个普通 C 字符串char str[]你从头到尾遍历它为每个字符创建一个新结点串到链尾。这里有一个小细节C 字符串末尾有\0\0要不要放进链串里我的建议是不放。原因有二一是 PTA 里打印链串时你看的是有效字符如果有\0结点遍历输出时反而要多一层判断二是替换算法中你操作的仅仅是有效字符区间单独把一个终止符作为结点放进去没有任何算法上的好处反而增加了删除和插入时的字符计数负担。所以链串的末尾结点 next 指向 NULL 即可这就等同于字符串的“结束标志”。如果你要写辅助函数我建议至少准备这几个createLinkString(char *s)用普通字符串创建链串displayLinkString(LinkStrNode *head)遍历打印链串linkStringLength(LinkStrNode *head)计算链串长度。这三个函数是后续实现替换算法的地基也是你在 PTA 调试时最依赖的工具。别嫌它们简单后面查 bug 的时候你就知道有多香了。3. 替换算法的核心思路从“暴力匹配”到“指针重连”现在切入正题链串替换算法到底怎么设计。我先把这题的标准描述复述一遍方便对照设计一个算法将链串 s 中所有与链串 t 相等的子串替换为链串 v。要求在原链串上进行操作不得借助顺序串的辅助空间输出的结果仍为链串。题目要求在原链串上操作这一点非常关键。这意味着你不能偷懒先把链串转成字符数组用顺序串的思路跑一遍替换再转回链串。这种“曲线救国”的写法虽然结果对但不符合题目的空间要求也没有体现链式结构的操作特征在考试或者面试里不会被认可。那么正确思路是什么样子我把它拆成三块来看查找、删除、插入。3.1 查找在链串中定位目标子串查找这一步本质上就是字符串模式匹配中的暴力匹配算法在链表上的变形。主串 s 用指针 p 遍历子串 t 用指针 q 遍历。每到一个新的起点 p 时我把 p 暂存到一个临时指针start中然后让 q 从 t 的头结点后第一个有效结点开始与 start 同步往后走逐字符比较。如果一路比较到 q 走到 NULL说明 t 串全部匹配成功那么从 start 到当前停下来的位置之间的这段结点就是我们要替换的目标段。如果中途某个字符不比配说明从 start 开始的这段不可能是目标子串于是 p 从 start 的下一个结点开始进入下一轮匹配。这个“从 start 的下一个结点重新开始”的操作在链串里对应的是p start-next。这里要特别提醒不要图省事写成p p-next。因为当比较失败时p 已经不在 start 的位置了它可能已经跑到 start 后面好几个结点去了。如果你直接 p p-next等于把起点跳过了漏掉了一种可能。举个例子s 是“aaa”t 是“aa”。第一个起点是 s 的第一个结点匹配成功后如果你直接把 p 移到被匹配段的尾部那下一轮匹配就会从第三个结点开始结果第二个起点匹配不到了最后只替换了一处。所以正确做法是每次匹配开始前记录 start不管匹配成功还是失败下一轮 p 都要从 start-next 开始。这样才是最朴素的、不重不漏的暴力匹配。3.2 删除把目标段从链子上摘下来找到目标段后我们要把它删除。这里的“删除”包含两层含义第一层是从链表中摘除让目标段前后结点直接相连第二层是释放被摘除结点的内存空间防止内存泄漏。两层缺一不可。有些同学只改了指针没有 free 结点这在小型测试用例里可能不会被发现但一旦涉及大量数据或者反复替换内存泄漏会越来越严重在某些评测环境下会因为内存超限而直接扣分。摘除操作的关键是记住目标段前一个位置的结点。我把它记为pre指针。在匹配过程中start 是目标段的第一个结点pre 是 start 的前一个结点。当我们确定要从 pre-next 一直删到 tail目标段的最后一个结点时先执行pre-next tail-next这一步就把目标段从整个链表中解开了目标段后面的那部分tail 之后的结点现在成了 pre 的下一个结点。接下来要回收目标段的内存。用一个临时指针temp从 start 开始逐个向后移动每移动一个结点就 free 一个。注意在 free 之前要先把下一步的地址存下来否则 free 之后你就找不到 next 了。代码模式如下LinkStrNode *temp start; while (temp ! tail-next) { LinkStrNode *nextNode temp-next; free(temp); temp nextNode; }有个细节很多人都没意识到tail 怎么获取在匹配过程中我们的 q 指向的是 t 串从头开始往后走的结点当 q 走到 NULL 时start 到某个位置的结点是匹配成功的。我们需要记录这个匹配的终点。我建议在匹配时维护两个指针start和end。start 指向匹配段的起点end 指向匹配段的最后一个结点。每次 start 和 q 同步比较成功一个字符end 就更新为 start 当前所在的位置。匹配结束后end 自然就是目标段的最后一个结点。tail 其实就是 end 的别名看你怎么命名。3.3 插入把替换串的结点链接上去删除完成之后pre-next 已经指向目标段后面的部分链子上留下了一个“豁口”。接下来我们要把 v 串的所有有效字符结点插入到这个豁口上。插入的做法是从头遍历 v 串每遇到一个有效字符就创建一个新结点然后把新结点依次链接到 pre 后面。这个过程要用三个指针协作一个指针 cur 指向 v 串当前要复制的结点一个指针 newTail 指向新链的最后一个结点初始时和 pre 相同还有一个指针 newNode 指向每次新创建的结点。每创建一个 newNode就让newTail-next newNode然后 newTail 更新为 newNode。这样所有的新结点就串联起来了。循环结束后把newTail-next pre-next也就是让新串的尾结点接上之前豁口后面留下的那部分结点。这样一来新串就完整地嵌入了原链串。千万不要忘了v 串本身是一棵独立的链串你不能直接把它的头结点或者首个结点嫁接到原链串上。因为那样会破坏 v 串本身的结构而且如果题目还要继续使用原 v 串就会出现数据共享导致的意想不到的后果。安全做法永远是创建新结点、逐个复制字符。这也是链表操作的一个基本原则你要“值”而不是要“地址”时就复制结点。3.4 循环与终止处理“所有匹配项”PTA 要求替换所有匹配的子串所以整个查找-删除-插入的过程要放在一个大循环里。大循环的终止条件是主串指针 p 已经遍历到链串末尾p 为 NULL。不过这里有个很有意思的边界问题替换完成之后p 应该指向哪里题目中没有明说但在“替换所有子串”的要求下比较安全的做法是让 p 指向新插入部分的第一个结点然后继续匹配。也就是说插入完成后我们并不跳跃到豁口后面的部分而是从新串的第一个字符开始继续尝试匹配。为什么这样做举个极端的例子s 串是“aa”t 是“a”v 是“aa”。如果你替换第一个“a”后把 p 直接跳到原串的第二个字符那最终结果是“aa”后接原来的“a”变成“aaa”其中前两个“a”其实是新插入的“aa”。这没问题。但如果你要求的是所有原串中的“a”都被替换而新插入的“aa”里也可能出现“a”那这个结果就取决于题目对“所有”的定义——是“原串中所有匹配位置”还是“替换完成后的最终串中所有匹配位置”。通常数据结构教材和 PTA 题目都默认前者即不递归处理新插入的内容避免死循环。像我刚说的 s“aa”、t“a”、v“aa”如果对新插入内容继续匹配那“aa”中间又会出现“a”替换后又变成“aa”……无限递归。所以必须停止对新插入内容的继续匹配。实现上插入完成后让 p 从豁口后面的原串结点开始继续遍历即可。具体到代码里你可以这样处理插入完成后记录nextStart newTail-next这就是豁口之后原串接下来的部分的第一个结点。然后把大循环指针 p 赋值为 nextStart继续下一轮匹配。这是一个非常实用的经验能帮你避开很多诡异的死循环和重复替换问题。4. 完整代码实现从结构到主函数的逐步落地讲了这么多思路是时候给出一个可以直接在 PTA 环境里跑通的完整实现了。我手写了一个版本把前面提到的每个细节都落实在代码里。你拿去提交前建议先照着思路过一遍再决定是否照抄——因为 PTA 的题目描述可能有细微差别比如头结点是否标准、输出格式要求等你需要做对应微调。但核心的替换函数replace部分基本是这个套路。#include stdio.h #include stdlib.h #include string.h typedef struct LNode { char data; struct LNode *next; } LinkStrNode; // 创建链串从普通字符串 str 构造带头结点的链串 LinkStrNode *createLinkString(char *str) { LinkStrNode *head (LinkStrNode *)malloc(sizeof(LinkStrNode)); head-next NULL; LinkStrNode *tail head; for (int i 0; str[i] ! \0; i) { LinkStrNode *node (LinkStrNode *)malloc(sizeof(LinkStrNode)); node-data str[i]; node-next NULL; tail-next node; tail node; } return head; } // 输出链串 void displayLinkString(LinkStrNode *head) { LinkStrNode *p head-next; while (p ! NULL) { putchar(p-data); p p-next; } putchar(\n); } // 计算链串长度 int linkStringLength(LinkStrNode *head) { int len 0; LinkStrNode *p head-next; while (p ! NULL) { len; p p-next; } return len; } // 在链串 s 中将所有与 t 相等的子串替换为 v void replace(LinkStrNode *s, LinkStrNode *t, LinkStrNode *v) { if (s NULL || t NULL || v NULL || t-next NULL) { return; } LinkStrNode *p s-next; // 主串遍历指针 LinkStrNode *pre s; // p 的前驱结点 while (p ! NULL) { LinkStrNode *start p; // 本轮匹配的起点 LinkStrNode *q t-next; // 模式串 t 的遍历指针 LinkStrNode *end NULL; // 匹配段的最后一个有效结点 // 从 start 开始和 q 逐字符比较 LinkStrNode *cur start; while (q ! NULL cur ! NULL) { if (cur-data q-data) { end cur; cur cur-next; q q-next; } else { break; } } // q NULL 表示 t 串完全匹配成功 if (q NULL) { // 1. 摘除 [start, end] 这一段 pre-next end-next; // 2. 释放摘除结点的内存 LinkStrNode *temp start; while (temp ! end-next) { LinkStrNode *nextNode temp-next; free(temp); temp nextNode; } // 3. 将 v 串的结点复制并插入到 pre 后面 LinkStrNode *newTail pre; LinkStrNode *vCur v-next; while (vCur ! NULL) { LinkStrNode *newNode (LinkStrNode *)malloc(sizeof(LinkStrNode)); newNode-data vCur-data; newNode-next NULL; newTail-next newNode; newTail newNode; vCur vCur-next; } // 4. 新串尾部接上原串剩余部分 newTail-next end-next; // 5. 下一轮从原串剩余部分的第一个结点开始继续匹配 p end-next; pre newTail; } else { // 匹配失败p 和 pre 都向前移动一个结点 pre p; p p-next; } } } int main() { char s[100], t[100], v[100]; // 输入 S 串 scanf(%s, s); // 输入 T 串 scanf(%s, t); // 输入 V 串 scanf(%s, v); LinkStrNode *sLink createLinkString(s); LinkStrNode *tLink createLinkString(t); LinkStrNode *vLink createLinkString(v); replace(sLink, tLink, vLink); displayLinkString(sLink); // 释放内存完整的实现还应包括释放 sLink、tLink、vLink 的辅助函数 return 0; }这个版本里有几个地方我想特别解释一下。首先replace函数中t-next NULL的判断是用来处理 t 是空串的情况。空串没有可匹配的内容直接返回即可。否则进入匹配流程q 一开始为空很容易造成空匹配所以提前拦掉。其次pre指针的维护是整个函数最容易写错的地方。匹配失败时pre 应该从 p 的位置挪到 p 的下一个位置但你不能直接把 pre 挪到 cur 停下来的位置因为 cur 可能已经走了好几步了。我代码里的写法是失败时pre 更新为 p当前这一轮匹配的起点然后 p 更新为 p-next。这样就实现了“从匹配起点的下一个结点重新开始”的语义。如果匹配成功pre 要保持指向新插入串的最后一个结点这样才能保证后续的匹配中如果需要再次摘除结点pre 能正确指向要被删的那段的前驱。我在代码里匹配成功后的最后写了pre newTail;这个语句很多人会漏掉漏掉的后果是下一轮匹配如果又遇到匹配成功删除结点时 pre 还指向旧位置链子就断错了。再次关于删除和插入的顺序我的做法是先摘除、再释放、再插入、最后接尾部。这个顺序很关键。如果你先插入再释放那么 free 目标段结点时新插入的结点的 next 会指向已经被释放的内存形成悬垂指针。而我的顺序中插入完成后直接把 newTail-next 指向 end-next因为 end-next 在此之前已经被保存好在第一步摘除时pre-next 已经被改成 end-next但 end-next 这个指针值依然有效它指向原串剩余部分。这就是链表操作的奥妙改变指针指向不等于改变了被指向的东西。还有一个容易埋雷的细节end-next在第一步摘除之后原目标段最后一个结点 end 虽然已经被摘出了链外但它的 next 仍然保留着原串剩余部分的地址所以我在插入完成后能放心引用end-next。这里我用的是它的值不需要 end 这个结点本身还在链上。这就是“摘除”和“释放”之间那一小段时间窗口里的信息保留。5. 踩坑记录与快速定位这些 bug 你真的可能遇到代码给出来了但不代表你照着写就一定一次通过。PTA 的评测点往往在你想不到的边界上等着你。我把这些年批改和自测中常见的错误整理成一份清单每一类我都见过至少三次绝对是高频重灾区。5.1 匹配成功却始终不输出替换结果这种问题多半出在主串指针 p 的推进逻辑上。多数同学的错误版本是这样的匹配失败时让p p-next匹配成功时也让p p-next。表面看没问题但一旦出现“成功匹配后 p 正好指向目标段的最后一个结点”那么 p 的下一轮起点就是目标段后面那个结点没有遗漏。而如果你在匹配成功后发现 p 指向的是 end 而不是 start 的下一个位置就会少匹配一些情况。用“aaa”和“aa”这个经典用例去测试就能立刻暴露问题。最好的检查方法是在每个分支给 p 赋值后手工模拟几个小用例看看 p 是否覆盖了所有可能的起点。5.2 替换后链串出现“断裂”或“环”断裂一般是因为没有把新串的尾结点接回原串剩余部分。环则是因为你在摘除目标段前忘了把 pre-next 断开导致新插入的结点接到了一个仍然指向目标段内部的链子上。这两种 bug 我在调试时最喜欢用“一个长度为 10 的链串输出前 20 个结点”的办法来检查。如果输出超过 10 个字符还在继续那基本就是成环了。如果你写代码时对每个 free 之前的 next 都先保存再操作这类问题会少很多。5.3 内存重复释放当你把目标段摘除后如果连续走到两个匹配位置而第一个位置释放的过程中你错误地把end-next也当成了目标段的一部分给 free 掉了那么第二个位置的 pre 就会指向非法内存。这种问题不容易在结果上看到异常但一旦把代码搬到带内存检测的环境比如 Valgrind 或者 PTA 的严格模式就会报出 “double free” 或 “invalid free”。写这类代码时建议每次 free 一个结点前先明确这个结点是否已经脱离了主链表还要确定它不会被后续操作再次引用。5.4 空串和单字符特殊情况v 是空串时替换操作本质上是删除所有匹配的 t 子串。这个情况要特别小心v 串没有有效结点插入循环一次都不会执行但你还是要把目标段摘除并释放然后把 pre 和 p 的关系正确维护好。如果 v 串的表示是一个只有头结点、next 为 NULL 的链串代码里那个 while (vCur ! NULL) 循环自然跳过newTail 就还是 prenewTail-next end-next 照样把链子接好所以我的代码天然支持空 v 串。这也是为什么我坚持用带头结点的链串结构——空串的处理变得非常自然。5.5 t 等于 v 时怎么办如果 t 和 v 是同一个字符串比如 s“abc”、t“b”、v“b”那这个替换操作应该等于什么也不做。但如果你在代码里每次匹配成功后都执行删除再插入那么你会把原来的“b”结点删掉再新建一个“b”结点。结果虽然一样但白白浪费了时间和空间。更关键的是如果你的删除逻辑里有任何破绽这种“同替换”的情况就会暴露出来。我在实际测试中遇到过学生写的代码在 tv 的情况下把 s 中所有 b 删光了原因就是删除之后 p 的移动位置不对。所以测试用例里务必加上这一条。5.6 连续匹配导致漏替换s“aaaa”t“aa”v“bb”。第一次从第 1 个字符开始匹配成功替换了前两个字符为“bb”剩下原串第 3、4 个字符“aa”。第二次 p 从原串第 3 个字符开始又匹配成功替换为“bb”最后结果是“bbbb”。这个逻辑是正确的。但如果你在第一次匹配成功后把 p 设置为 end-next 之前忘了把 pre 更新为 newTail第二次匹配时 pre 还指向原串第 0 个位置的结点一删除就会把新插入的“bb”后面的一段给误删掉。这就是我前面反复强调 pre 更新必要性的原因。下面是一个排查对照表你可以把它当作“急救手册”来用现象最可能的原因快速检查方法替换后少了一段内容摘除目标段时删多了或 pre 位置错误打印摘除前 pre-next 的值和 end-next 对比替换后输出出现重复字符插入结点的 next 没接回剩余部分打印 newTail-next 是否为 end-next多次替换时漏匹配p 移动的位置跳过了一个可能的起点用 s“aaa”, t“aa” 验证程序运行非常慢但结果正确暴力匹配在长串上的正常表现也可能存在多余循环使用长 1000 的随机串测试估算耗时运行时崩溃访问了已释放结点常见于 end-next 被 free 后仍引用检查释放前是否保存了 end-next死循环 / 输出截断替换后 p 没有向后推进加计数器限制最大循环次数调试6. 链串替换的变式与扩展为什么不建议用“重建法”到这里标准解题思路已经讲完了。但我知道很多同学在接触这类题时脑子里冒出的第一个想法其实是干脆把链串转成字符数组在数组里做替换完事再转回链串。这个方法我称之为“重建法”。它在功能上确实可行尤其在数据量不大的时候还特别容易写对。但我强烈不建议你在 PTA 这道题里用它原因有三层。第一层是题目要求。PTA 的“串的算法设计”系列明确强调链式存储的应用而不只是结果正确。评测时虽然不检查你是否真的“在原链串上操作”数据结构课程的练习目的摆在那里你用顺序串的思路完成链串作业本质上是用数组解决了链表题没有练到该练的能力。第二层是性能。重建法需要遍历链串转数组又要在数组里做可能触发多次元素搬移的替换最后还要遍历数组重新建链。对于长串和多次替换来说这比纯粹的链上操作要多出不少常数开销。虽然在 O 记号下两者的渐进复杂度可能接近但实际常数差异在数据量大时非常明显。第三层是面试场景。很多公司的面试官喜欢拿链表题目当手写代码题链串替换就是很典型的变种。你在白板上写一个重建法面试官一眼就能看出你没有真正理解链表的优势但如果你能写出“匹配-摘除-插入”的版本同时再解释清楚为什么不直接嫁接到 v 串是因为数据共享问题那面试官对你的评价会完全不一样。链串替换本身还能延伸出好几个变式值得你继续想想仅替换第一次出现大循环改成找到第一个匹配后直接 return逻辑上更简单。大小写不敏感匹配比较字符时统一用 tolower 转换即可。交叉匹配处理比如 s 是“ababa”t 是“aba”寻找所有不重叠的匹配结果应该是 1 个而不是 2 个。因为重叠匹配会导致替换结果非常诡异。我代码里每次匹配成功后 p 跳到 end-next天然避开了重叠匹配这是大多数题目默认的语义。替换计数函数加一个计数器返回替换次数这在统计类题目里很实用。块链串版本每个结点存多个字符匹配和删除都需要处理块内偏移。这个变式能帮你彻底理解“物理连续”和“逻辑连续”的差别但代码量会大很多不推荐作为第一轮学习目标。我自己在实际做题时还有几个小小的习惯想分享。第一个习惯是给链串写一个“可视化打印”函数比如printf(s: ); displayLinkString(s)每次替换操作前后都打印一遍肉眼就能看出哪里断链。第二个习惯是准备一组固定的小测试用例包括空串、单字符、完全匹配、部分匹配、多次匹配、t 和 v 等长、v 比 t 长、v 比 t 短这八种情况每次写完代码都跑一遍。这八种情况基本覆盖了所有边界分支能挡住九成以上的低级错误。第三个习惯是每次 free 一个结点之后立刻把它的 next 置为 NULL。虽然这不是必须的但能防止某些情况下二次 free 时误判。如果你在调试时发现替换后的链串少了一段不要急着全面检查代码。先在删除和插入的边界打两个断点第一个在摘除后打印pre-next和pre的关系第二个在插入结束后打印newTail-next。看到这两个指针的状态问题基本就定位了。这种“分段验证”的思路比从头到尾逐行读代码高效得多。链串替换这道题做透了你对“串”这一章的理解绝对会上一个台阶。它看起来只是链表的增删查改但真正动手写一遍你会发现指针的前后关系、内存的申请释放、边界条件的处理每一个环节都在考验你的工程思维。就像厨师切菜菜刀也就那么多用法但切丝、切片、切丁的每一刀都有讲究。链串替换里的每一根指针就是你的刀工。做完这道题再去碰 KMP 算法优化子串匹配你会觉得链表版的匹配逻辑亲切得多——因为 KMP 解决的是“匹配失败后快速回退”的问题而在链串里回退本身就是最昂贵的操作。理解了这个痛点你才算真正入门了字符串算法设计。