# 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 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。