PTA习题11-8“单链表结点删除”光听名字像是一道送分题遍历链表把值为x的结点摘掉谁还不会可在咱们这些被链表毒打过的同学眼里这个题至少有三个看不见的坑头结点谁来删、连续重复怎么删、free之后指针还能不能用。这篇就把这个题从里到外拆开从最简单的删一个结点开始一路写到删光所有x的完整模板顺便把带头结点和不带头结点的两套写法讲清楚。不管你是正在刷PTA的在校生还是期末前临时抱佛脚的初学者被这道题卡住都不是智商问题而是链表这玩意儿的调试手段本来就不如数组直观。我会把每一版代码怎么来的、为什么这么写的理由都讲透你照着抄完再自测三个用例心里基本就有底了。1. 别急着写循环先拆穿这道题的三道暗坎1.1 链表删除的本质是“改挂钩”不是“删数据”很多同学第一次写删除结点的代码思路是“找到x然后把那个结点干掉”。这个直觉方向没错但落实到C语言指针上就变味了。单链表每个结点长这样typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList;每个结点里有一个data存数据有一个next指针指向下一个结点。多个结点串起来就像一列火车每个车厢尾部有个挂钩勾住下一节车厢。删除一个结点物理上要做两件事让前一个车厢的挂钩绕过这个车厢直接勾住它的后一节车厢。把这个车厢本身释放掉free还给系统。所以“删除”的本质是改前驱结点的next指针而不是拿着目标结点本身去操作。你要delete的是谁直接影响操作方式但真正改的永远是它前一个结点的指针。这一点想不通后面写出来的代码全是靠运气过测试点。1.2 三道暗坎分别是什么第一道坎头结点没有前驱。如果x正好是第一个结点的值你根本没有“前驱”可以改。这时候要么单独写一个分支要么让函数返回新的头指针要么用二级指针从外面把头结点换掉。第二道坎连续重复。链表是2-2-3要求删掉所有值为2的结点很多人删掉第一个2之后又把前驱指针往后挪了结果第二个2成了新的“头结点”又单独处理一次乱了。正确做法是删除操作完成后当前指针往后走、前驱指针原地不动。第三道坎free之后继续访问。这是C语言新手最常见的翻车现场。有人写free(cur); cur cur-next;逻辑上看起来是先释放再往后走可实际上free之后cur已经变成悬空指针再读cur-next是未定义行为。在本地跑可能“碰巧没崩”提交到PTA平台上可能就是段错误或者输出结果时好时坏。这三道坎不是传说中的“难题套路”而是链表删除操作的真正常见场景。PTA这类题目的测试点也基本围绕它们来设。典型评测情况写着写着容易在哪里翻车删除普通中间结点改了pre-next却忘记更新cur删除头结点没有处理头结点无前驱的情况删除连续重复结点删除后前驱指针被误挪漏删删除尾结点free之后还访问next或data链表为空没判空就直接访问data链表里没有x遍历结束后一切正常但返回值写错我建议你把这张表存一下写代码之前先对着检查一遍比一个测试点一个测试点去试错高效得多。2. 从“删一个”说起带前驱指针的遍历怎么写才不乱2.1 一次只删一个值为x的结点我们先不贪心先写一个“只删除第一个值为x的结点”的函数。虽然习题最终要求是删光所有x但从单删除入手能把指针移动的基本功练扎实。题目里链表是不带头结点的函数签名如果是LinkList deleteNode(LinkList L, int x)返回删除后的头指针代码就是下面这个样子LinkList deleteNode(LinkList L, int x) { // 1. 先处理头结点就是目标的情况 if (L ! NULL L-data x) { LinkList tmp L; L L-next; free(tmp); return L; } // 2. 处理非头结点pre永远指向cur的前驱 LinkList pre L; LinkList cur L-next; while (cur ! NULL) { if (cur-data x) { pre-next cur-next; free(cur); break; } pre cur; cur cur-next; } return L; }这段代码最需要看明白的是第二部分。我在遍历时用了两个指针pre是前驱cur是当前结点。只有当cur的值不等于x时两者才一起往后挪一旦发现cur的值等于x直接让pre-next跳过cur然后break退出。为什么不让pre一直等于cur的前一个因为删除这个动作需要前驱。带着pre走就是为了在找到目标时能立刻拿到它的前驱不需要再从头扫一遍。2.2 为什么头结点要单独写分支头结点没有前驱这是单链表结构决定的。指针操作完如果目标在第一个位置那新的头指针应该是原来第二个结点的指针。如果你不把新头传回去调用者手里的L还是指着那块已经被free的内存链表就彻底丢了。所以我在函数开头先判断L-data x同时要求L不为空。这个L ! NULL不是摆设链表为空时你再写L-data就是空指针访问PTA直接给你个段错误。你也可以用另一种思路加一个虚拟头结点让所有结点都有前驱。这个技巧在后面第4节会讲到它能把头结点的特殊分支消掉让代码更统一。2.3 只有cur不行的原因在哪有人会问我只用一个cur指针找到目标后调用free(cur)再让curcur-next看起来不也挺顺的吗问题出在“让前一个结点指向下一个结点”这一步。你没有前驱指针就没法让前一个结点的next指向目标的下一个。除非你乐意从头再遍历一遍但那相当于每次删除都O(n)变成O(n^2)不是这道题的本意。另一个隐藏问题是free之后立即cur cur-next。这一步语法能过但语义是错的free以后cur内存已经被释放读它的next成员是非法的。正确的过程必须先把next存出来再free再让cur走到存好的next上LinkList next cur-next; pre-next next; free(cur); cur next;这个“先保存next再改链接最后释放”的顺序就是链表删除的基本操作。后面所有删除场景都逃不开这个节奏。3. 删光所有x的核心删除之后cur走、pre不走3.1 从“删一个”改到“删所有”只差一点点把上面的函数改成“删除所有值为x的结点”逻辑上最直观的变化是找到目标后不break继续往后走。但如果你只是机械地把break去掉马上会在连续重复的数据上栽跟头。先看一个错误示范while (cur ! NULL) { if (cur-data x) { pre-next cur-next; free(cur); cur cur-next; pre pre-next; // 这个多余的更新 } else { pre cur; cur cur-next; } }这段代码在链表为2-2-3、x2时只删掉了第一个2。原因正是红色注释那一步删除第一个2后cur移动到原来的第二个2pre也往后移动到了原来的第二个2的位置。但此时pre原本指向的结点已经被删了新的pre其实是新的“头结点”而cur还站在第二个2那里。下次循环cur和pre指向同一个结点再比较cur-data x发现是2又执行pre-next cur-next……可是pre和cur指向同一个结点这个赋值等于把cur的next指向了cur自己链表当场变形。正确做法是在删除分支里pre保持原地不动while (cur ! NULL) { if (cur-data x) { pre-next cur-next; free(cur); cur pre-next; } else { pre cur; cur cur-next; } }为什么pre不动因为删除一个结点后pre的下一个结点已经换成了cur原来的next。你并不知道这个新next是不是也要删。如果pre急着往前走就跳过了这个待检查的新节点。只有确定当前cur不需要删除时才让pre和cur一起往前走。3.2 用一道连续重复的例子走一遍链表1 → 2 → 2 → 3 → NULLx2。循环次数删除前pre删除前cur操作删除后链表11第一个2pre-next指向第二个2free第一个21 → 2 → 321第二个2pre-next指向3free第二个21 → 3313值不相等pre3curNULL1 → 3看第2次循环pre依然是1没有动。这样才能把第二个2也删掉。这个细节就是考题想考你的“核心操作”。3.3 最终版删光所有x的不带头结点函数下面给出一个完整可提交的版本使用二级指针能处理头结点也是x的情况void deleteAll(LinkList *L, int x) { if (L NULL || *L NULL) { return; } LinkList pre NULL; LinkList cur *L; while (cur ! NULL) { if (cur-data x) { LinkList tmp cur; if (pre NULL) { // 删除的是头结点更新*L *L cur-next; } else { pre-next cur-next; } cur cur-next; free(tmp); } else { pre cur; cur cur-next; } } }这里用LinkList *L而不是LinkList L是为了让函数能修改实参里的头指针。如果你写成void deleteAll(LinkList L, int x)函数里面改L L-next是没用的调用者手里的头指针不会变。这是初学者最容易忽略的C语言参数传递问题指针也是值传递。当然如果你不喜欢二级指针也可以写一个返回LinkList的函数在函数里返回新的头指针调用处再赋值回去。两种风格在PTA里都能过取决于题目给的是哪种函数签名。3.4 不要搞错free和取next的先后我在这个函数的free(tmp)之前先执行了cur cur-next然后把tmp释放。这个顺序看起来很别扭但很安全。因为tmp和cur在那一刻指向同一个结点你必须先进去把next取出来存到cur里再free。另一种更清晰的写法是LinkList next cur-next; if (pre NULL) { *L next; } else { pre-next next; } free(cur); cur next;这样临时变量多了一个但可读性更好。我实际写代码时更喜欢这种因为“先取next再改链最后释放”三步顺序非常直观不容易出错。4. 带头结点和不带头结点两套模板一次说清4.1 带头结点的链表为什么更省心头结点head node不是第一个数据结点它的data通常不存东西next才指向第一个真正有数据的结点。这样做的最大好处是链表永远有一个“虚拟前驱”删除第一个数据结点时不需要特殊处理直接改头结点的next就行。带头结点的删除所有x代码简洁很多void deleteAllWithHead(LinkList L, int x) { if (L NULL) { return; } LinkList pre L; LinkList cur L-next; while (cur ! NULL) { if (cur-data x) { pre-next cur-next; free(cur); cur pre-next; } else { pre cur; cur cur-next; } } }注意看这里完全没有判断“删除的是否是头结点”的分支。因为pre一开始就是头结点这个哨兵cur是第一个数据结点。就算把第一个数据结点删了pre头结点还在链表结构依然完整。这就是哨兵节点的价值。4.2 不带头结点的链表必须处理头指针变动不带头结点时空表就是L NULL第一个结点就是数据结点。删除操作必须时刻想着“头指针是否要变”。二级指针版本我在前面已经给了其实还有一种写法是不用二级指针、但通过返回值更新头指针LinkList deleteAll(LinkList L, int x) { LinkList pre NULL; LinkList cur L; while (cur ! NULL) { if (cur-data x) { LinkList tmp cur; if (pre NULL) { L cur-next; } else { pre-next cur-next; } cur cur-next; free(tmp); } else { pre cur; cur cur-next; } } return L; }调用时就是L deleteAll(L, x);。两种方式效果一样看题目接口。4.3 两套模板到底区别在哪比较项带头结点不带头结点空表判断L-next NULLL NULL删除头结点头结点不参与数据无需特殊处理需要单独分支或更新头指针接口设计通常传LinkList即可要看二级指针或返回值代码长度较短逻辑统一多一个头部分支容易忘PTA题目如果不专门指明“带头结点”默认就是最原始的不带头结点形式。你做题前要先看main函数怎么创建的链表如果LinkList L; LNULL;那是不带头结点如果L(LinkList)malloc(sizeof(LNode)); L-nextNULL;那就是带头结点。4.4 一种更省心的写法临时虚拟头结点如果你发现自己在不带头结点的版本里总是搞不定头指针有个取巧但完全有效的办法在函数内部创建一个虚拟头结点让它的next指向L然后统一按带头结点的方式处理最后把新头传回来LinkList deleteAllByHead(LinkList L, int x) { LinkList dummy (LinkList)malloc(sizeof(LNode)); dummy-next L; LinkList pre dummy; LinkList cur L; while (cur ! NULL) { if (cur-data x) { pre-next cur-next; free(cur); cur pre-next; } else { pre cur; cur cur-next; } } L dummy-next; free(dummy); return L; }这个技巧的实质是自己造一个前驱把“删头结点”这个特殊场景抹掉。它在很多链表算法题里都非常实用建议熟练掌握。5. 从调试器里捞回来的教训连续重复、尾删、空链表5.1 现场一连续重复数据只删了单数位我最初写删除所有x的时候犯过前面说的经典错误——删除分支里多写了一行pre pre-next。当时测试用例用的链表是2-2-2-3x2结果输出里居然还剩一个2。第一次看到这个输出我的反应是“循环条件错了”其实不是。后来我在关键位置插了printfprintf(pre%d cur%d\n, pre-data, cur-data);输出清晰地显示第一次删除后pre和cur指向同一个结点第二个2被漏掉了。这就是为什么删除后pre不能动的原因。这个问题的隐蔽性在于单个x时代码表现完全正常你很难意识到删除分支里多了一步更新是错的。只有上连续重复数据才会暴露。5.2 现场二free之后还去读next程序时好时坏另一个特别恶心的bug是free后继续访问。我见过很多同学把删除代码写成free(cur); pre-next cur-next;先释放再读next。这在有些编译环境里不报错因为free只是把内存标记为可用内容还没立刻被改动。但一旦那块内存被其他变量重新分配你读到的东西就是错的。更糟的是链表一旦被破坏后续打印整个链表都会崩。修法很简单把free放到最后执行先保存next再改连接再free。顺序一定不能乱。5.3 现场三空链表直接判data还有人在函数开头直接写if (L-data x) { ... }如果链表为空L是NULL访问L-data立刻段错误。这种错误在本地跑空表时会立刻暴露但如果测试点没有空表你可能完全注意不到。PTA的测试点一定会包含空链表场景所以判空不能省。我自己的检查习惯是写完函数后先用三个用例自测空链表。链表第一个结点就是要删的结点。链表里有连续重复的x。这三个用例过了这道题大概率就稳了。你不需要记住所有边界情况但一定要把这三个最典型的场景跑一遍因为它覆盖了链表删除题里90%的坑。6. 把这道题的写法沉淀成模板后续链表题事半功倍6.1 一套能反复用的套路前驱指针保存next这道题做完了真正值得带走的不是某一行代码而是一套思考模板。以后遇到任何链表删除操作先问自己三句话要删除的结点可能是头结点吗怎么处理头指针删除后当前指针应该指向哪里前驱指针动不动释放内存之前有没有先把next保存下来把这三句话背下来比记住任何一份答案都有用。因为PTA里链表删除的衍生题本质上都是这三句话的组合。6.2 变式一删除倒数第N个结点这类题用双指针一个快指针先走N步然后慢指针跟着走。快指针到链表尾部时慢指针正好停在要删结点前一个位置。接下来就是标准的pre-next修改操作跟本题一模一样。核心难点只是“怎么让快指针先走N步”删除动作本身零变化。6.3 变式二有序链表去重有序链表中重复值连续出现要求只保留一个。很多人以为是“比较当前结点和下一个结点”但我建议直接用本题框架遇到相同值就删除当前结点pre不动遇到不同值pre和cur一起走。这样代码和本题几乎完全一样只是判断条件从cur-data x改成cur-data cur-next-data。换个条件思路一模一样。6.4 变式三把链表按值分成两段再拼接比如“将链表中小于x的结点放在大于等于x的结点之前”本质上是拆链和接链但拆链时仍然用pre、cur、next三个指针。你只要把本题的指针操作练熟再接触这种题就会觉得顺理成章。6.5 最后再说点我的实际体会我帮很多师弟师妹debug链表题发现大家最常犯的错不是不会写而是“写了就提交没想过自己测”。链表这东西光靠大脑模拟特别容易出错但画一画、printf打一打问题很快就能定位。PTA上的反馈只有红叉绿勾不会告诉你到底错在哪所以自己掌握一套自测方法才是关键。这道题做完以后我强烈建议你把带头结点和不带头结点的两套代码都保留下来以后碰到不同接口的题目直接改两行就能用。链表删除的核心操作就那么多练到肌肉记忆后面的习题会轻松很多。