拓冰网站定制 
LeetCode 86. 分隔链表Partition List题解Python/Java/C 双链表指针法与源码级解析【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book本篇指南围绕《Krahets 笔面试精选 88 题》中 86. 分隔链表 这一经典链表题展开。你将掌握新建两个链表 双指针遍历 拼接的核心解法理解哑节点dummy node为何能简化边界处理并通过仓库中 Python / Java / C 三语源码与测试用例验证解法的正确性与复杂度结论。读完可直接在 LeetCode 上复现该题解并迁移到同类按条件重组链表的问题中。题目核心在保持相对顺序的前提下按值 x 分割链表题目要求对单链表head进行分割使得所有值小于x的节点都出现在值大于等于x的节点之前同时保留两部分节点各自原有的相对顺序。这里有两个容易被忽略的关键约束正是它们决定了算法的形态不要求排序分割不是排序 x部分和 x部分内部无需按值大小排列只需满足小的在前、大的在后。相对顺序保持原链表中先出现的节点在分割后仍应排在前面。这意味着不能简单地对值排序后重建链表。例如经典测试用例[1, 4, 3, 2, 5, 2]x 3分割结果应为[1, 2, 2, 4, 3, 5] 3的1, 2, 2在前且保持原顺序 3的4, 3, 5在后且保持原顺序。解法思路新建两个链表遍历拆分后拼接原题解文档给出的核心策略是新建两个链表分别收集两类节点具体分为四步新建两个链表sml_dummy、big_dummy分别用于挂载「节点值 x」与「节点值 x」的节点遍历链表head逐节点比较head.val与x若head.val x把该节点追加到sml_dummy链表末尾若head.val x把该节点追加到big_dummy链表末尾遍历结束后把sml_dummy的链表尾与big_dummy的第一个有效节点big_dummy.next拼接返回sml_dummy.next作为新链表头。整个过程只需一次遍历每步操作均为常数时间因此时间复杂度为O(N)只使用了两个哑节点和两个移动指针额外空间为O(1)。原文档也明确给出这两项复杂度结论时间复杂度 O(N)遍历链表使用线性时间、空间复杂度 O(1)假头节点使用常数大小的额外空间。为什么必须使用哑节点统一头节点与尾节点的边界处理解法中sml_dummy与big_dummy被称为假头节点dummy head其核心价值在于消除链表为空时头节点不存在的特判若不用哑节点sml链表在第一个 x节点到来前没有实际头节点插入时需要额外判断链表是否为空、头节点指向谁使用ListNode(0)作为占位头后插入逻辑统一为tail.next node; tail tail.next无需任何条件分支最终返回sml_dummy.next即真实头节点若sml部分为空sml_dummy.next恰好指向big部分的头天然处理了全部节点都 x的边界情况。这一哑节点统一边界的技巧在仓库其他链表题中同样高频出现例如 21. 合并两个有序链表、160. 相交链表 等属于链表题最值得沉淀的通用范式。关键细节为什么最后必须执行big.next None拼接完成后代码有一行容易被初学者忽略的收尾big.next NonePython/big.next nullJava/big-next nullptrC。这一步必不可少原因是遍历过程中节点只是被挂载到新链表但其原有的next指针并未被清空原链表中的最后一个节点可能位于sml部分且其next仍指向big部分的某个节点若不清空就会形成环或使结果链表出现非预期的后续节点显式置空big.next后big链表即结果链表真正的尾部以None收尾保证结果是一条合法的单链表。同理代码中sml.next big_dummy.next之所以拼接的是big_dummy.next而非big_dummy也是因为big_dummy只是占位节点真正的 x部分从头节点big_dummy.next开始。三语言实现仓库源码逐行对照原文档提供了 Python、Java、C 三种语言的解法代码仓库中 selected_coding_interview/codes 目录则保存了带测试驱动的完整可运行版本每道题均提供_s1基础版与_s2注释版两个文件。三份核心实现逻辑完全一致class Solution: def partition(self, head: Optional[ListNode], x: int) - Optional[ListNode]: sml_dummy, big_dummy ListNode(0), ListNode(0) sml, big sml_dummy, big_dummy while head: if head.val x: sml.next head sml sml.next else: big.next head big big.next head head.next sml.next big_dummy.next big.next None return sml_dummy.nextclass Solution { public ListNode partition(ListNode head, int x) { ListNode smlDummy new ListNode(0), bigDummy new ListNode(0); ListNode sml smlDummy, big bigDummy; while (head ! null) { if (head.val x) { sml.next head; sml sml.next; } else { big.next head; big big.next; } head head.next; } sml.next bigDummy.next; big.next null; return smlDummy.next; } }class Solution { public: ListNode* partition(ListNode* head, int x) { ListNode *smlDummy new ListNode(0), *bigDummy new ListNode(0); ListNode *sml smlDummy, *big bigDummy; while (head ! nullptr) { if (head-val x) { sml-next head; sml sml-next; } else { big-next head; big big-next; } head head-next; } sml-next bigDummy-next; big-next nullptr; return smlDummy-next; } };三份代码在结构上完全同构sml/big两个指针分别指向两条链表的当前末尾循环内仅做一次值比较、一次挂载、一次指针前进。值得注意的要点比较边界head.val x走sml分支else即 x走big分支保证了题目要求的 x在前、 x在后的分界点语义遍历驱动每轮循环末尾head head.next将原链表指针前移直至遍历完所有节点拼接与收尾先sml.next big_dummy.next完成两部分连接再big.next None截断多余引用。源码级验证测试用例与可运行驱动代码原文档给出的是 LeetCode 提交版仅Solution类而仓库在 selected_coding_interview/codes/python/lc_86_partition_list_s1.py 中补充了可直接运行的完整测试驱动便于本地验证结果from include import * # Solution Code class Solution: def partition(self, head: Optional[ListNode], x: int) - Optional[ListNode]: ... # Test Case # Test case 1: Basic linked list head list_to_linked_list([1, 4, 3, 2, 5, 2]) x 3 # Driver Code slt Solution() result slt.partition(head, x) print_linked_list(result)运行后应输出1 - 2 - 2 - 4 - 3 - 5与题目示例预期一致。仓库中配套的基础设施包括链表节点的定义与构造工具 linked_list.py提供ListNode类、list_to_linked_list数组转链表与linked_list_to_list链表转数组便于断言比对打印工具 print_util.pyprint_linked_list以a - b - c形式输出链表方便肉眼核对结果Java 与 C 版本同样包含main驱动与打印逻辑见 lc_86_partition_list_s1.java 与 lc_86_partition_list_s1.cpp测试用例均为[1, 4, 3, 2, 5, 2]、x 3。复杂度与正确性总结维度结论依据时间复杂度O(N)N 为链表长度单次遍历每节点常数次操作空间复杂度O(1)仅两个哑节点与两个游标指针正确性遍历保证两部分内相对顺序不变节点按原顺序依次追加到各自链表末尾边界覆盖空链表、全 x、全 x均安全哑节点 最终big.next None收尾本题是双指针 哑节点模板在链表重组问题中的典型应用与仓库中 142. 环形链表 II、206. 反转链表 等题共享同一套操作指针而非创建新节点的思维模式——本题没有申请任何新节点只是重新编排了既有节点的引用关系这也是它能做到 O(1) 额外空间的根本原因。掌握这一思路后遇到按奇偶拆分链表按值分组重排等变体题即可直接套用。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 86. 分隔链表（Partition List）题解：Python/Java/C++ 双链表指针法与源码级解析
LeetCode 86. 分隔链表Partition List题解Python/Java/C 双链表指针法与源码级解析【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book本篇指南围绕《Krahets 笔面试精选 88 题》中 86. 分隔链表 这一经典链表题展开。你将掌握新建两个链表 双指针遍历 拼接的核心解法理解哑节点dummy node为何能简化边界处理并通过仓库中 Python / Java / C 三语源码与测试用例验证解法的正确性与复杂度结论。读完可直接在 LeetCode 上复现该题解并迁移到同类按条件重组链表的问题中。题目核心在保持相对顺序的前提下按值 x 分割链表题目要求对单链表head进行分割使得所有值小于x的节点都出现在值大于等于x的节点之前同时保留两部分节点各自原有的相对顺序。这里有两个容易被忽略的关键约束正是它们决定了算法的形态不要求排序分割不是排序 x部分和 x部分内部无需按值大小排列只需满足小的在前、大的在后。相对顺序保持原链表中先出现的节点在分割后仍应排在前面。这意味着不能简单地对值排序后重建链表。例如经典测试用例[1, 4, 3, 2, 5, 2]x 3分割结果应为[1, 2, 2, 4, 3, 5] 3的1, 2, 2在前且保持原顺序 3的4, 3, 5在后且保持原顺序。解法思路新建两个链表遍历拆分后拼接原题解文档给出的核心策略是新建两个链表分别收集两类节点具体分为四步新建两个链表sml_dummy、big_dummy分别用于挂载「节点值 x」与「节点值 x」的节点遍历链表head逐节点比较head.val与x若head.val x把该节点追加到sml_dummy链表末尾若head.val x把该节点追加到big_dummy链表末尾遍历结束后把sml_dummy的链表尾与big_dummy的第一个有效节点big_dummy.next拼接返回sml_dummy.next作为新链表头。整个过程只需一次遍历每步操作均为常数时间因此时间复杂度为O(N)只使用了两个哑节点和两个移动指针额外空间为O(1)。原文档也明确给出这两项复杂度结论时间复杂度 O(N)遍历链表使用线性时间、空间复杂度 O(1)假头节点使用常数大小的额外空间。为什么必须使用哑节点统一头节点与尾节点的边界处理解法中sml_dummy与big_dummy被称为假头节点dummy head其核心价值在于消除链表为空时头节点不存在的特判若不用哑节点sml链表在第一个 x节点到来前没有实际头节点插入时需要额外判断链表是否为空、头节点指向谁使用ListNode(0)作为占位头后插入逻辑统一为tail.next node; tail tail.next无需任何条件分支最终返回sml_dummy.next即真实头节点若sml部分为空sml_dummy.next恰好指向big部分的头天然处理了全部节点都 x的边界情况。这一哑节点统一边界的技巧在仓库其他链表题中同样高频出现例如 21. 合并两个有序链表、160. 相交链表 等属于链表题最值得沉淀的通用范式。关键细节为什么最后必须执行big.next None拼接完成后代码有一行容易被初学者忽略的收尾big.next NonePython/big.next nullJava/big-next nullptrC。这一步必不可少原因是遍历过程中节点只是被挂载到新链表但其原有的next指针并未被清空原链表中的最后一个节点可能位于sml部分且其next仍指向big部分的某个节点若不清空就会形成环或使结果链表出现非预期的后续节点显式置空big.next后big链表即结果链表真正的尾部以None收尾保证结果是一条合法的单链表。同理代码中sml.next big_dummy.next之所以拼接的是big_dummy.next而非big_dummy也是因为big_dummy只是占位节点真正的 x部分从头节点big_dummy.next开始。三语言实现仓库源码逐行对照原文档提供了 Python、Java、C 三种语言的解法代码仓库中 selected_coding_interview/codes 目录则保存了带测试驱动的完整可运行版本每道题均提供_s1基础版与_s2注释版两个文件。三份核心实现逻辑完全一致class Solution: def partition(self, head: Optional[ListNode], x: int) - Optional[ListNode]: sml_dummy, big_dummy ListNode(0), ListNode(0) sml, big sml_dummy, big_dummy while head: if head.val x: sml.next head sml sml.next else: big.next head big big.next head head.next sml.next big_dummy.next big.next None return sml_dummy.nextclass Solution { public ListNode partition(ListNode head, int x) { ListNode smlDummy new ListNode(0), bigDummy new ListNode(0); ListNode sml smlDummy, big bigDummy; while (head ! null) { if (head.val x) { sml.next head; sml sml.next; } else { big.next head; big big.next; } head head.next; } sml.next bigDummy.next; big.next null; return smlDummy.next; } }class Solution { public: ListNode* partition(ListNode* head, int x) { ListNode *smlDummy new ListNode(0), *bigDummy new ListNode(0); ListNode *sml smlDummy, *big bigDummy; while (head ! nullptr) { if (head-val x) { sml-next head; sml sml-next; } else { big-next head; big big-next; } head head-next; } sml-next bigDummy-next; big-next nullptr; return smlDummy-next; } };三份代码在结构上完全同构sml/big两个指针分别指向两条链表的当前末尾循环内仅做一次值比较、一次挂载、一次指针前进。值得注意的要点比较边界head.val x走sml分支else即 x走big分支保证了题目要求的 x在前、 x在后的分界点语义遍历驱动每轮循环末尾head head.next将原链表指针前移直至遍历完所有节点拼接与收尾先sml.next big_dummy.next完成两部分连接再big.next None截断多余引用。源码级验证测试用例与可运行驱动代码原文档给出的是 LeetCode 提交版仅Solution类而仓库在 selected_coding_interview/codes/python/lc_86_partition_list_s1.py 中补充了可直接运行的完整测试驱动便于本地验证结果from include import * # Solution Code class Solution: def partition(self, head: Optional[ListNode], x: int) - Optional[ListNode]: ... # Test Case # Test case 1: Basic linked list head list_to_linked_list([1, 4, 3, 2, 5, 2]) x 3 # Driver Code slt Solution() result slt.partition(head, x) print_linked_list(result)运行后应输出1 - 2 - 2 - 4 - 3 - 5与题目示例预期一致。仓库中配套的基础设施包括链表节点的定义与构造工具 linked_list.py提供ListNode类、list_to_linked_list数组转链表与linked_list_to_list链表转数组便于断言比对打印工具 print_util.pyprint_linked_list以a - b - c形式输出链表方便肉眼核对结果Java 与 C 版本同样包含main驱动与打印逻辑见 lc_86_partition_list_s1.java 与 lc_86_partition_list_s1.cpp测试用例均为[1, 4, 3, 2, 5, 2]、x 3。复杂度与正确性总结维度结论依据时间复杂度O(N)N 为链表长度单次遍历每节点常数次操作空间复杂度O(1)仅两个哑节点与两个游标指针正确性遍历保证两部分内相对顺序不变节点按原顺序依次追加到各自链表末尾边界覆盖空链表、全 x、全 x均安全哑节点 最终big.next None收尾本题是双指针 哑节点模板在链表重组问题中的典型应用与仓库中 142. 环形链表 II、206. 反转链表 等题共享同一套操作指针而非创建新节点的思维模式——本题没有申请任何新节点只是重新编排了既有节点的引用关系这也是它能做到 O(1) 额外空间的根本原因。掌握这一思路后遇到按奇偶拆分链表按值分组重排等变体题即可直接套用。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考