文档教程知识库【免费下载链接】algorithm-base一位酷爱做饭的程序员立志用动画将算法说的通俗易懂。我的面试网站 www.chengxuchu.com项目地址https://gitcode.com/gh_mirrors/al/algorithm-base点击查看免费下载导读本文以 algorithm-base 仓库链表篇的 leetcode86分隔链表.md 为主体完整讲解 LeetCode 86「分隔链表」这一经典面试题。全文围绕先分后合的核心思路展开用两个哑节点哨兵节点分别收集「小于 x」与「大于等于 x」的节点最后将两条链表拼接并切断 big 链表的尾部防止成环。读完本文你将掌握单链表分组重排类题目的通用套路理解哑节点与尾指针截断这两个关键细节并得到六种主流语言的可直接运行代码可与仓库内同类的链表拼接题如剑指 Offer 25、LeetCode 328横向对照。一、题目回顾86. 分隔链表1.1 题目描述给你一个链表的头节点head和一个特定值x请你对链表进行分隔使得所有小于 x的节点都出现在大于或等于 x的节点之前。你应当保留两个分区中每个节点的初始相对位置。这道题来自力扣LeetCode第 86 题是链表分组重排类题目中最具代表性的一道经常出现在面试与算法练习中。它不要求改变节点内的值只要求通过调整节点间的指针指向来重排链表因此是对链表指针操作能力的一次直接考察。1.2 示例示例 1输入head [1,4,3,2,5,2], x 3 输出[1,2,2,4,3,5]示例 2输入head [2,1], x 2 输出[1,2]从示例 1 可以看出值小于 3 的节点1、2、2全部排在前面且它们之间的相对顺序1 → 2 → 2与原链表一致值大于等于 3 的节点4、3、5排在后面相对顺序4 → 3 → 5也保持不变。稳定性保留初始相对位置是本题区别于按值分组排序的关键约束。二、解题思路将链表先分后合2.1 核心思想原文档给出的核心思想非常凝练就四个字先分后合。具体拆解如下创建一个侦察兵指针pro从链表头部出发逐个遍历节点负责比较每个节点的值与x的大小关系。两个哑节点作为容器头值 x的节点依次接到big链表大值链表上值 x的节点依次接到small链表小值链表上。一个细节至关重要遍历结束后将big链表的尾部指针置为null否则可能形成环。合将small链表的尾部和big链表的第一个有效节点相连返回small链表的第一个有效节点。整个过程可以概括为先通过一次遍历把原链表拆成两条链表再通过一次指针赋值把它们拼回去。2.2 为什么不能原地边摘边插有的读者可能会想能不能不建新链表直接在原链表上把小于x的节点一个个摘下来插到前面从单链表的结构看这种做法的难点在于单链表只能单向访问删除一个节点需要同时持有其前驱节点的指针节点被摘除后前驱与后继的衔接需要额外处理插入位置小值链表的尾部也需要维护一个专门的尾指针。虽然这样做也能 AC但指针操作的边界条件明显更多容易出错。相比之下先分后合用两个哑节点把大值、小值分两条链收集遍历结束后只需一次拼接逻辑更清晰、更不容易出 bug——这正是本题解选择该方案的原因。2.3 哑节点哨兵节点的作用代码中的big、small都是值为-1的哑节点new ListNode(-1)它们的作用有三点统一处理空链表情况即使某个分组一个节点都没有哑节点本身也始终存在后续的headbig.next/headsmall.next取值永远是安全的值为null也不会越界避免特殊判断头节点因为新链表的头节点位置不确定取决于第一个小于 x 的节点在哪用哑节点可以让所有节点都按尾部追加的统一方式接入无需单独处理第一次插入的分支方便返回结果最终返回headsmall.next即小值链表的第一个有效节点。关于ListNode的定义与初始化方式可以参考仓库中的 Leetcode常用类和函数.md 链表篇说明ListNode list new ListNode(0)即初始化一个指定值的空节点本题中用-1作为哑节点的占位值其本身不参与结果输出。三、关键细节big.next null防止成环3.1 为什么会成环这是本题最容易忽略、也最重要的一个细节。原文档明确指出最后一个细节就是我们的 big 链表尾部要加上 null不然会形成环。原因分析如下在分的过程中big.next pro只是把pro这个节点接入big 链表的尾部但并没有断开pro原有的 next 指向。也就是说大值链表的最后一个节点它的next可能还挂着原链表中后续的节点。举一个具体的例子输入head [4, 1]x 3。原链表结构为4 - 1 - null遍历到44 3接入 big此时 big 链表为-1 - 4而4.next仍然指向1遍历到11 3接入 smallsmall 链表为-1 - 1此时如果不做big.next null直接执行small.next headbig.next得到的结果是1 - 4 - 1 - 4 - ...链表出现环既不是合法结果也可能导致后续遍历或输出时死循环。3.2 什么时候必须执行从上面的分析可以得出结论只要原链表的最后一个节点是小于 x 的节点而 big 链表中又接入了更早的大值节点那么 big 链表尾部的next就会残留指向小值节点的指针此时big.next null是必须的。反过来如果原链表最后一个节点本身属于 big 分组 x它的next原本就是null此时执行big.next null也不会产生任何副作用。结论无论哪种情况统一在合并前执行big.next null都是安全且必要的这是先分后合方案正确的最后一块拼图。四、动画模拟与逐行拆解仓库中以动画模拟作为核心讲解手段README 中将本题归入【动画模拟】链表篇原文档配套有完整的模拟动图。下面我们用示例 1 手工推演一遍完整流程等价于把动画的每一帧用文字复现出来。4.1 用示例 1 逐步推演输入head [1,4,3,2,5,2]x 3。步骤侦察兵 pro判断执行操作small 链表big 链表初始化1—创建哑节点-1-1111 3small 接入 1-1 - 1-1244 3big 接入 4-1 - 1-1 - 4333 3big 接入 3-1 - 1-1 - 4 - 3422 3small 接入 2-1 - 1 - 2-1 - 4 - 3555 3big 接入 5-1 - 1 - 2-1 - 4 - 3 - 5622 3small 接入 2-1 - 1 - 2 - 2-1 - 4 - 3 - 5结束null—big.next null切断残留指针-1 - 1 - 2 - 2-1 - 4 - 3 - 5 - null合并——small.next headbig.next结果1 - 2 - 2 - 4 - 3 - 5最终输出[1,2,2,4,3,5]与题目示例完全一致。注意第 3 步中3 3说明等于 x 的节点被归入 big 分组这正符合题目大于或等于 x 的节点在前者之后的要求。4.2 指针的角色划分以 Java 代码为例可以清晰地看到每个指针的职责pro侦察兵遍历原链表big/small两条分组链表的尾部指针始终指向各自分组的最后一个节点用于追加新节点headbig/headsmall哑节点的备份指针因为big、small会随着追加不断移动需要另外保存头位置供最后拼接与返回使用。这种尾指针移动 头指针备份的写法是链表拼接类问题的标准模式与仓库中 剑指Offer25合并两个排序的链表.md 中headpro/headtemp的分工如出一辙。五、六语言完整实现以下代码完整继承自原文档六种语言逻辑完全一致分while 遍历→ 截断big 尾置空→ 合small 接 big→ 返回headsmall.next。5.1 Javaclass Solution { public ListNode partition(ListNode head, int x) { ListNode pro head; ListNode big new ListNode(-1); ListNode small new ListNode(-1); ListNode headbig big; ListNode headsmall small; //分 while (pro ! null) { //大于时放到 big 链表上 if (pro.val x) { big.next pro; big big.next; //小于时放到 small 链表上 }else { small.next pro; small small.next; } pro pro.next; } //细节 big.next null; //合 small.next headbig.next; return headsmall.next; } }5.2 Cclass Solution { public: ListNode* partition(ListNode* head, int x) { ListNode * pro head; ListNode * big new ListNode(-1); ListNode * small new ListNode(-1); ListNode * headbig big; ListNode * headsmall small; //分 while (pro ! nullptr) { //大于时放到 big 链表上 if (pro-val x) { big-next pro; big big-next; //小于时放到 small 链表上 }else { small-next pro; small small-next; } pro pro-next; } //细节 big-next nullptr; //合 small-next headbig-next; return headsmall-next; } };5.3 JavaScriptvar partition function (head, x) { let pro head; let big new ListNode(-1); let small new ListNode(-1); let headbig big; let headsmall small; //分 while (pro) { //大于时放到 big 链表上 if (pro.val x) { big.next pro; big big.next; //小于时放到 small 链表上 } else { small.next pro; small small.next; } pro pro.next; } //细节 big.next null; //合 small.next headbig.next; return headsmall.next; };5.4 Pythonclass Solution: def partition(self, head: ListNode, x: int) - ListNode: pro head big ListNode(-1) small ListNode(-1) headbig big headsmall small # 分 while pro is not None: # 大于时放到 big 链表上 if pro.val x: big.next pro big big.next # 小于时放到 small 链表上 else: small.next pro small small.next pro pro.next # 细节 big.next None # 合 small.next headbig.next return headsmall.next5.5 Swiftclass Solution { func partition(_ head: ListNode?, _ x: Int) - ListNode? { var pro head var big ListNode(-1) var small ListNode(-1) var headbig big var headsmall small //分 while pro ! nil { //大于时放到 big 链表上 if pro!.val x { big.next pro big big.next! //小于时放到 small 链表上 } else { small.next pro small small.next! } pro pro?.next } //细节 big.next nil //合 small.next headbig.next return headsmall.next } }5.6 Gofunc partition(head *ListNode, x int) *ListNode { big, small : ListNode{}, ListNode{} headBig, headSmall : big, small temp : head for temp ! nil { // 分开存 if temp.Val x { small.Next temp small small.Next } else { big.Next temp big big.Next } temp temp.Next } // 最后一个节点指向nil big.Next nil // 存小数的链表和存大数的连起来 small.Next headBig.Next return headSmall.Next }六、复杂度与边界情况分析6.1 时间复杂度与空间复杂度时间复杂度O(n)其中 n 为链表节点总数。整个算法只对链表做一次完整遍历分阶段合阶段只进行常数次指针赋值不产生额外遍历空间复杂度O(1)。只额外创建了big、small两个哑节点常数个指针变量没有使用与节点数相关的额外存储空间属于典型的原地in-place重排。6.2 边界情况验证对几种典型边界输入可以基于代码逻辑直接验证其正确性输入处理过程结果head nullwhile 循环不执行big.next nullsmall.next headbig.next null返回null正确单节点且val x节点进 smallbig.next nullsmall.next headbig.next null返回该节点正确单节点且val x节点进 bigbig.next nullsmall.next headbig.next指向该节点返回该节点正确全部节点 x如[3,4,5], x3全部进 bigbig.next null切断尾部small.next headbig.next指向原链表头返回原链表[3,4,5]相对顺序不变正确全部节点 x如[1,2], x3全部进 smallbig 只有哑节点small.next null返回原链表[1,2]正确节点值等于 x如[3], x33 3进 big归入大于等于分组符合题意可以看出由于哑节点的存在空链表与某分组为空的情况都被自然兼容代码无需额外写 if 分支处理这正是该写法鲁棒性的体现。七、举一反三仓库中的同类链表拼接题目分组 → 拼接的思路在链表类题目中非常通用algorithm-base 仓库的 链表篇 目录下就有多道可以横向对照的题目7.1 剑指 Offer 25合并两个排序的链表剑指Offer25合并两个排序的链表.md 与本题共享了三个核心技巧哑节点headpre/headpro作为结果链表的统一接入点避免头节点空判断尾指针移动每接入一个节点尾指针后移一位剩余链表整体拼接一链表遍历完后把另一链表剩余部分整体接上headpro.next l1 ! null ? l1 : l2。区别在于合并两个有序链表是双指针竞争较小值而分隔链表是单指针按值与 x 比较分流。二者结合阅读可以完整掌握用哑节点构造新链表这一类问题的解法骨架。7.2 LeetCode 328奇偶链表leetcode328奇偶链表.md 是本题思路的变式不是按值与 x 的大小分组而是按节点位置奇数位/偶数位分组最后同样将两组链表拼接odd.next evenHead。它同样需要处理尾部截断类细节并且把空间复杂度限制为 O(1)。把两道题放在一起对比就能理解分组条件只是变量而先分后合的框架是稳定的。7.3 LeetCode 206反转链表leetcode206反转链表.md 提供了最基础的指针操作训练temp.next low、low temp等三指针滑动它是理解本题big.next pro这类指针重新指向操作的前提。仓库原文也提示链表题目考察的是代码的完整性和鲁棒性建议把链表题目都亲手写一遍想清每一行代码的作用。八、总结LeetCode 86「分隔链表」虽然是一道中等难度的链表题但它的价值在于把一个常见需求——按条件把链表节点重排并保持相对顺序——用最简洁的方式实现出来。回顾全文的关键点思路先分后合。一次遍历 两次拼接逻辑清晰、不易出错哑节点用big、small两个哨兵节点消除头节点特殊判断让空链表与空分组自动兼容防环细节big.next null必须执行否则原链表尾节点残留的 next 指针会让结果成环复杂度时间 O(n)、空间 O(1)原地完成重排通用性该套路在仓库的 剑指Offer25合并两个排序的链表.md、leetcode328奇偶链表.md 中反复出现值得作为链表专题的必练模板之一。建议读者对照原文档 leetcode86分隔链表.md 中的动画模拟配合本文的逐步推演表亲手将六种语言的代码各写一遍——正如仓库作者所强调的链表题目看着思路简单想直接通过还是需要下一番功夫。赞分享文档教程知识库【免费下载链接】algorithm-base一位酷爱做饭的程序员立志用动画将算法说的通俗易懂。我的面试网站 www.chengxuchu.com项目地址https://gitcode.com/gh_mirrors/al/algorithm-base点击查看免费下载相关推荐LeetCode 86. 分隔链表Partition List题解Python/Java/C 双链表指针法与源码级解析LeetCode 86. 分隔链表Partition List题解Python/Java/C 双链表指针法与源码级解析 本篇指南围绕《Krahets示例工程security-audit-skill 路线图展望AI 安全审计还缺哪些能力社区在期待什么security audit skill 路线图展望AI 安全审计还缺哪些能力社区在期待什么 security audit skill 是一个面向编码智能体AI 技能应用安全LeetCode 86. 分隔链表Partition List题解双虚拟节点拆分合并法LeetCode 86. 分隔链表Partition List题解双虚拟节点拆分合并法 本文是「leetcode 解题之路」系列中 86. 分隔链表 ht文档教程知识库上一篇Rust CLI 实战指南用 clap color-eyre tracing indicatif dialoguer 构建生产级命令行工具下一篇DeepSeek-V3代码生成实战从环境配置到API调用的完整开发指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 algorithm-base 动画图解 LeetCode 86：分隔链表 ——“先分后合“思路与 Java / C++ / JS / Python / Swift / Go 六语言实现
文档教程知识库【免费下载链接】algorithm-base一位酷爱做饭的程序员立志用动画将算法说的通俗易懂。我的面试网站 www.chengxuchu.com项目地址https://gitcode.com/gh_mirrors/al/algorithm-base点击查看免费下载导读本文以 algorithm-base 仓库链表篇的 leetcode86分隔链表.md 为主体完整讲解 LeetCode 86「分隔链表」这一经典面试题。全文围绕先分后合的核心思路展开用两个哑节点哨兵节点分别收集「小于 x」与「大于等于 x」的节点最后将两条链表拼接并切断 big 链表的尾部防止成环。读完本文你将掌握单链表分组重排类题目的通用套路理解哑节点与尾指针截断这两个关键细节并得到六种主流语言的可直接运行代码可与仓库内同类的链表拼接题如剑指 Offer 25、LeetCode 328横向对照。一、题目回顾86. 分隔链表1.1 题目描述给你一个链表的头节点head和一个特定值x请你对链表进行分隔使得所有小于 x的节点都出现在大于或等于 x的节点之前。你应当保留两个分区中每个节点的初始相对位置。这道题来自力扣LeetCode第 86 题是链表分组重排类题目中最具代表性的一道经常出现在面试与算法练习中。它不要求改变节点内的值只要求通过调整节点间的指针指向来重排链表因此是对链表指针操作能力的一次直接考察。1.2 示例示例 1输入head [1,4,3,2,5,2], x 3 输出[1,2,2,4,3,5]示例 2输入head [2,1], x 2 输出[1,2]从示例 1 可以看出值小于 3 的节点1、2、2全部排在前面且它们之间的相对顺序1 → 2 → 2与原链表一致值大于等于 3 的节点4、3、5排在后面相对顺序4 → 3 → 5也保持不变。稳定性保留初始相对位置是本题区别于按值分组排序的关键约束。二、解题思路将链表先分后合2.1 核心思想原文档给出的核心思想非常凝练就四个字先分后合。具体拆解如下创建一个侦察兵指针pro从链表头部出发逐个遍历节点负责比较每个节点的值与x的大小关系。两个哑节点作为容器头值 x的节点依次接到big链表大值链表上值 x的节点依次接到small链表小值链表上。一个细节至关重要遍历结束后将big链表的尾部指针置为null否则可能形成环。合将small链表的尾部和big链表的第一个有效节点相连返回small链表的第一个有效节点。整个过程可以概括为先通过一次遍历把原链表拆成两条链表再通过一次指针赋值把它们拼回去。2.2 为什么不能原地边摘边插有的读者可能会想能不能不建新链表直接在原链表上把小于x的节点一个个摘下来插到前面从单链表的结构看这种做法的难点在于单链表只能单向访问删除一个节点需要同时持有其前驱节点的指针节点被摘除后前驱与后继的衔接需要额外处理插入位置小值链表的尾部也需要维护一个专门的尾指针。虽然这样做也能 AC但指针操作的边界条件明显更多容易出错。相比之下先分后合用两个哑节点把大值、小值分两条链收集遍历结束后只需一次拼接逻辑更清晰、更不容易出 bug——这正是本题解选择该方案的原因。2.3 哑节点哨兵节点的作用代码中的big、small都是值为-1的哑节点new ListNode(-1)它们的作用有三点统一处理空链表情况即使某个分组一个节点都没有哑节点本身也始终存在后续的headbig.next/headsmall.next取值永远是安全的值为null也不会越界避免特殊判断头节点因为新链表的头节点位置不确定取决于第一个小于 x 的节点在哪用哑节点可以让所有节点都按尾部追加的统一方式接入无需单独处理第一次插入的分支方便返回结果最终返回headsmall.next即小值链表的第一个有效节点。关于ListNode的定义与初始化方式可以参考仓库中的 Leetcode常用类和函数.md 链表篇说明ListNode list new ListNode(0)即初始化一个指定值的空节点本题中用-1作为哑节点的占位值其本身不参与结果输出。三、关键细节big.next null防止成环3.1 为什么会成环这是本题最容易忽略、也最重要的一个细节。原文档明确指出最后一个细节就是我们的 big 链表尾部要加上 null不然会形成环。原因分析如下在分的过程中big.next pro只是把pro这个节点接入big 链表的尾部但并没有断开pro原有的 next 指向。也就是说大值链表的最后一个节点它的next可能还挂着原链表中后续的节点。举一个具体的例子输入head [4, 1]x 3。原链表结构为4 - 1 - null遍历到44 3接入 big此时 big 链表为-1 - 4而4.next仍然指向1遍历到11 3接入 smallsmall 链表为-1 - 1此时如果不做big.next null直接执行small.next headbig.next得到的结果是1 - 4 - 1 - 4 - ...链表出现环既不是合法结果也可能导致后续遍历或输出时死循环。3.2 什么时候必须执行从上面的分析可以得出结论只要原链表的最后一个节点是小于 x 的节点而 big 链表中又接入了更早的大值节点那么 big 链表尾部的next就会残留指向小值节点的指针此时big.next null是必须的。反过来如果原链表最后一个节点本身属于 big 分组 x它的next原本就是null此时执行big.next null也不会产生任何副作用。结论无论哪种情况统一在合并前执行big.next null都是安全且必要的这是先分后合方案正确的最后一块拼图。四、动画模拟与逐行拆解仓库中以动画模拟作为核心讲解手段README 中将本题归入【动画模拟】链表篇原文档配套有完整的模拟动图。下面我们用示例 1 手工推演一遍完整流程等价于把动画的每一帧用文字复现出来。4.1 用示例 1 逐步推演输入head [1,4,3,2,5,2]x 3。步骤侦察兵 pro判断执行操作small 链表big 链表初始化1—创建哑节点-1-1111 3small 接入 1-1 - 1-1244 3big 接入 4-1 - 1-1 - 4333 3big 接入 3-1 - 1-1 - 4 - 3422 3small 接入 2-1 - 1 - 2-1 - 4 - 3555 3big 接入 5-1 - 1 - 2-1 - 4 - 3 - 5622 3small 接入 2-1 - 1 - 2 - 2-1 - 4 - 3 - 5结束null—big.next null切断残留指针-1 - 1 - 2 - 2-1 - 4 - 3 - 5 - null合并——small.next headbig.next结果1 - 2 - 2 - 4 - 3 - 5最终输出[1,2,2,4,3,5]与题目示例完全一致。注意第 3 步中3 3说明等于 x 的节点被归入 big 分组这正符合题目大于或等于 x 的节点在前者之后的要求。4.2 指针的角色划分以 Java 代码为例可以清晰地看到每个指针的职责pro侦察兵遍历原链表big/small两条分组链表的尾部指针始终指向各自分组的最后一个节点用于追加新节点headbig/headsmall哑节点的备份指针因为big、small会随着追加不断移动需要另外保存头位置供最后拼接与返回使用。这种尾指针移动 头指针备份的写法是链表拼接类问题的标准模式与仓库中 剑指Offer25合并两个排序的链表.md 中headpro/headtemp的分工如出一辙。五、六语言完整实现以下代码完整继承自原文档六种语言逻辑完全一致分while 遍历→ 截断big 尾置空→ 合small 接 big→ 返回headsmall.next。5.1 Javaclass Solution { public ListNode partition(ListNode head, int x) { ListNode pro head; ListNode big new ListNode(-1); ListNode small new ListNode(-1); ListNode headbig big; ListNode headsmall small; //分 while (pro ! null) { //大于时放到 big 链表上 if (pro.val x) { big.next pro; big big.next; //小于时放到 small 链表上 }else { small.next pro; small small.next; } pro pro.next; } //细节 big.next null; //合 small.next headbig.next; return headsmall.next; } }5.2 Cclass Solution { public: ListNode* partition(ListNode* head, int x) { ListNode * pro head; ListNode * big new ListNode(-1); ListNode * small new ListNode(-1); ListNode * headbig big; ListNode * headsmall small; //分 while (pro ! nullptr) { //大于时放到 big 链表上 if (pro-val x) { big-next pro; big big-next; //小于时放到 small 链表上 }else { small-next pro; small small-next; } pro pro-next; } //细节 big-next nullptr; //合 small-next headbig-next; return headsmall-next; } };5.3 JavaScriptvar partition function (head, x) { let pro head; let big new ListNode(-1); let small new ListNode(-1); let headbig big; let headsmall small; //分 while (pro) { //大于时放到 big 链表上 if (pro.val x) { big.next pro; big big.next; //小于时放到 small 链表上 } else { small.next pro; small small.next; } pro pro.next; } //细节 big.next null; //合 small.next headbig.next; return headsmall.next; };5.4 Pythonclass Solution: def partition(self, head: ListNode, x: int) - ListNode: pro head big ListNode(-1) small ListNode(-1) headbig big headsmall small # 分 while pro is not None: # 大于时放到 big 链表上 if pro.val x: big.next pro big big.next # 小于时放到 small 链表上 else: small.next pro small small.next pro pro.next # 细节 big.next None # 合 small.next headbig.next return headsmall.next5.5 Swiftclass Solution { func partition(_ head: ListNode?, _ x: Int) - ListNode? { var pro head var big ListNode(-1) var small ListNode(-1) var headbig big var headsmall small //分 while pro ! nil { //大于时放到 big 链表上 if pro!.val x { big.next pro big big.next! //小于时放到 small 链表上 } else { small.next pro small small.next! } pro pro?.next } //细节 big.next nil //合 small.next headbig.next return headsmall.next } }5.6 Gofunc partition(head *ListNode, x int) *ListNode { big, small : ListNode{}, ListNode{} headBig, headSmall : big, small temp : head for temp ! nil { // 分开存 if temp.Val x { small.Next temp small small.Next } else { big.Next temp big big.Next } temp temp.Next } // 最后一个节点指向nil big.Next nil // 存小数的链表和存大数的连起来 small.Next headBig.Next return headSmall.Next }六、复杂度与边界情况分析6.1 时间复杂度与空间复杂度时间复杂度O(n)其中 n 为链表节点总数。整个算法只对链表做一次完整遍历分阶段合阶段只进行常数次指针赋值不产生额外遍历空间复杂度O(1)。只额外创建了big、small两个哑节点常数个指针变量没有使用与节点数相关的额外存储空间属于典型的原地in-place重排。6.2 边界情况验证对几种典型边界输入可以基于代码逻辑直接验证其正确性输入处理过程结果head nullwhile 循环不执行big.next nullsmall.next headbig.next null返回null正确单节点且val x节点进 smallbig.next nullsmall.next headbig.next null返回该节点正确单节点且val x节点进 bigbig.next nullsmall.next headbig.next指向该节点返回该节点正确全部节点 x如[3,4,5], x3全部进 bigbig.next null切断尾部small.next headbig.next指向原链表头返回原链表[3,4,5]相对顺序不变正确全部节点 x如[1,2], x3全部进 smallbig 只有哑节点small.next null返回原链表[1,2]正确节点值等于 x如[3], x33 3进 big归入大于等于分组符合题意可以看出由于哑节点的存在空链表与某分组为空的情况都被自然兼容代码无需额外写 if 分支处理这正是该写法鲁棒性的体现。七、举一反三仓库中的同类链表拼接题目分组 → 拼接的思路在链表类题目中非常通用algorithm-base 仓库的 链表篇 目录下就有多道可以横向对照的题目7.1 剑指 Offer 25合并两个排序的链表剑指Offer25合并两个排序的链表.md 与本题共享了三个核心技巧哑节点headpre/headpro作为结果链表的统一接入点避免头节点空判断尾指针移动每接入一个节点尾指针后移一位剩余链表整体拼接一链表遍历完后把另一链表剩余部分整体接上headpro.next l1 ! null ? l1 : l2。区别在于合并两个有序链表是双指针竞争较小值而分隔链表是单指针按值与 x 比较分流。二者结合阅读可以完整掌握用哑节点构造新链表这一类问题的解法骨架。7.2 LeetCode 328奇偶链表leetcode328奇偶链表.md 是本题思路的变式不是按值与 x 的大小分组而是按节点位置奇数位/偶数位分组最后同样将两组链表拼接odd.next evenHead。它同样需要处理尾部截断类细节并且把空间复杂度限制为 O(1)。把两道题放在一起对比就能理解分组条件只是变量而先分后合的框架是稳定的。7.3 LeetCode 206反转链表leetcode206反转链表.md 提供了最基础的指针操作训练temp.next low、low temp等三指针滑动它是理解本题big.next pro这类指针重新指向操作的前提。仓库原文也提示链表题目考察的是代码的完整性和鲁棒性建议把链表题目都亲手写一遍想清每一行代码的作用。八、总结LeetCode 86「分隔链表」虽然是一道中等难度的链表题但它的价值在于把一个常见需求——按条件把链表节点重排并保持相对顺序——用最简洁的方式实现出来。回顾全文的关键点思路先分后合。一次遍历 两次拼接逻辑清晰、不易出错哑节点用big、small两个哨兵节点消除头节点特殊判断让空链表与空分组自动兼容防环细节big.next null必须执行否则原链表尾节点残留的 next 指针会让结果成环复杂度时间 O(n)、空间 O(1)原地完成重排通用性该套路在仓库的 剑指Offer25合并两个排序的链表.md、leetcode328奇偶链表.md 中反复出现值得作为链表专题的必练模板之一。建议读者对照原文档 leetcode86分隔链表.md 中的动画模拟配合本文的逐步推演表亲手将六种语言的代码各写一遍——正如仓库作者所强调的链表题目看着思路简单想直接通过还是需要下一番功夫。赞分享文档教程知识库【免费下载链接】algorithm-base一位酷爱做饭的程序员立志用动画将算法说的通俗易懂。我的面试网站 www.chengxuchu.com项目地址https://gitcode.com/gh_mirrors/al/algorithm-base点击查看免费下载相关推荐LeetCode 86. 分隔链表Partition List题解Python/Java/C 双链表指针法与源码级解析LeetCode 86. 分隔链表Partition List题解Python/Java/C 双链表指针法与源码级解析 本篇指南围绕《Krahets示例工程security-audit-skill 路线图展望AI 安全审计还缺哪些能力社区在期待什么security audit skill 路线图展望AI 安全审计还缺哪些能力社区在期待什么 security audit skill 是一个面向编码智能体AI 技能应用安全LeetCode 86. 分隔链表Partition List题解双虚拟节点拆分合并法LeetCode 86. 分隔链表Partition List题解双虚拟节点拆分合并法 本文是「leetcode 解题之路」系列中 86. 分隔链表 ht文档教程知识库上一篇Rust CLI 实战指南用 clap color-eyre tracing indicatif dialoguer 构建生产级命令行工具下一篇DeepSeek-V3代码生成实战从环境配置到API调用的完整开发指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考