# 0086. 分隔链表 ## 题目地址(86. 分隔链表) <https://leetcode-cn.com/problems/partition-list/> ## 题目描述 ``` <pre class="calibre18">``` 给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。 你应当保留两个分区中每个节点的初始相对位置。 示例: 输入: head = 1->4->3->2->5->2, x = 3 输出: 1->2->2->4->3->5 ``` ``` ## 前置知识 - 链表 ## 公司 - 阿里 - 腾讯 - 百度 - 字节 ## 思路 - 设定两个虚拟节点，dummyHead1 用来保存小于该值的链表，dummyHead2 来保存大于等于该值的链表 - 遍历整个原始链表，将小于该值的放于 dummyHead1 中，其余的放置在 dummyHead2 中 遍历结束后，将 dummyHead2 插入到 dummyHead1 后面  (图片来自： <https://github.com/MisterBooo/LeetCodeAnimation>) ## 关键点解析 - 链表的基本操作（遍历） - 虚拟节点 dummy 简化操作 - 遍历完成之后记得`currentL1.next = null;`否则会内存溢出 > 如果单纯的遍历是不需要上面操作的，但是我们的遍历会导致 currentL1.next 和 currentL2.next 中有且仅有一个不是 null， 如果不这么操作的话会导致两个链表成环，造成溢出。 ## 代码 - 语言支持: Javascript，Python3 ``` <pre class="calibre18">``` <span class="hljs-title">/** * @param {ListNode} head * @param {number} x * @return {ListNode} */</span> <span class="hljs-keyword">var</span> partition = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">head, x</span>) </span>{ <span class="hljs-keyword">const</span> dummyHead1 = { next: <span class="hljs-params">null</span>, }; <span class="hljs-keyword">const</span> dummyHead2 = { next: <span class="hljs-params">null</span>, }; <span class="hljs-keyword">let</span> current = { next: head, }; <span class="hljs-keyword">let</span> currentL1 = dummyHead1; <span class="hljs-keyword">let</span> currentL2 = dummyHead2; <span class="hljs-keyword">while</span> (current.next) { current = current.next; <span class="hljs-keyword">if</span> (current.val < x) { currentL1.next = current; currentL1 = current; } <span class="hljs-keyword">else</span> { currentL2.next = current; currentL2 = current; } } currentL2.next = <span class="hljs-params">null</span>; currentL1.next = dummyHead2.next; <span class="hljs-keyword">return</span> dummyHead1.next; }; ``` ``` Python3 Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">partition</span><span class="hljs-params">(self, head: ListNode, x: int)</span> -> ListNode:</span> <span class="hljs-string">"""在原链表操作，思路基本一致，只是通过指针进行区分而已"""</span> <span class="hljs-title"># 在链表最前面设定一个初始node作为锚点，方便返回最后的结果</span> first_node = ListNode(<span class="hljs-params">0</span>) first_node.next = head <span class="hljs-title"># 设计三个指针，一个指向小于x的最后一个节点，即前后分离点</span> <span class="hljs-title"># 一个指向当前遍历节点的前一个节点</span> <span class="hljs-title"># 一个指向当前遍历的节点</span> sep_node = first_node pre_node = first_node current_node = head <span class="hljs-keyword">while</span> current_node <span class="hljs-keyword">is</span> <span class="hljs-keyword">not</span> <span class="hljs-keyword">None</span>: <span class="hljs-keyword">if</span> current_node.val < x: <span class="hljs-title"># 注意有可能出现前一个节点就是分离节点的情况</span> <span class="hljs-keyword">if</span> pre_node <span class="hljs-keyword">is</span> sep_node: pre_node = current_node sep_node = current_node current_node = current_node.next <span class="hljs-keyword">else</span>: <span class="hljs-title"># 这段次序比较烧脑</span> pre_node.next = current_node.next current_node.next = sep_node.next sep_node.next = current_node sep_node = current_node current_node = pre_node.next <span class="hljs-keyword">else</span>: pre_node = current_node current_node = pre_node.next <span class="hljs-keyword">return</span> first_node.next ``` ``` **复杂度分析** - 时间复杂度：O(N)O(N)O(N) - 空间复杂度：O(1)O(1)O(1) 大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。