删除链表中的节点

记住这八个字「复制后继、摘掉后继」,下面每一帧都在套它。顺序很重要:必须先复制值、再改指针。

链表是 4→5→1→9,要删的 node 是值 5 这个节点。常规做法得找到它前面的 4、把 4 的 next 改成指向 1;可我们手里只有 node,够不到前面的 4,这条路走不通。

换个角度,看 node 的后继:值 1 的节点(记作 succ)。既然删不掉 node 自己,那就把 succ 的内容搬到 node 上,再把 succ 删掉,从结果看一模一样。

第一步,复制值:把 succ 的值 1 写进 node。node 从 5 变成了 1,链表暂时是 4→1→1→9,出现两个 1,其中第一个 1 就是原来的 node。

第二步,改指针:让 node 的 next 跳过 succ、直接指向 succ 的后继(值 9)。succ(标红的第二个 1)就此脱离了链条。

succ 被摘出去后,链表收成 4→1→9。原来值 5 的位置现在是值 1,后面接着 9,中间那个多余的 1 已经没人指向它了。

删除完成:链表变成 4→1→9,等效地把原来的值 5 节点删掉了。全程没碰前驱、没遍历,只做了「复制一个值、改一个指针」两件事,O(1) 完成。

再看一个巩固:链表 2→4→6→8,删值 4 的节点。同样的两步走,自己跟着推一遍。

复制值:把后继 succ(值 6)的值搬进 node,node 由 4 变 6,链表暂成 2→6→6→8。

改指针并摘掉 succ:node 的 next 跳到值 8,多余的那个 6 被摘除,链表收成 2→6→8。删值 4 的节点完成,套路一模一样。

边界:必须是非尾节点(有后继才能复制);删倒数第二个也照常成立。

两个高频追问:为何删不了尾节点、被摘的其实是后继节点。