# 0328. 奇偶鏈表 ## 題目地址(328. 奇偶鏈表) <https://leetcode-cn.com/problems/odd-even-linked-list/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個單鏈表，把所有的奇數節點和偶數節點分別排在一起。請注意，這里的奇數節點和偶數節點指的是節點編號的奇偶性，而不是節點的值的奇偶性。 請嘗試使用原地算法完成。你的算法的空間復雜度應為 O(1)，時間復雜度應為 O(nodes)，nodes 為節點總數。 示例 1: 輸入: 1->2->3->4->5->NULL 輸出: 1->3->5->2->4->NULL 示例 2: 輸入: 2->1->3->5->6->4->7->NULL 輸出: 2->3->6->7->1->5->4->NULL 說明: 應當保持奇數節點和偶數節點的相對順序。 鏈表的第一個節點視為奇數節點，第二個節點視為偶數節點，以此類推。 ``` ``` ## 前置知識 - 鏈表 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 符合直覺的想法是，先遍歷一遍找出奇數的節點。然后再遍歷一遍找出偶數節點，最后串起來。 但是有兩個問題，如果不修改節點的話，需要借助額外的空間，空間復雜度是 N。如果修改的話，會對第二次遍歷（遍歷偶數節點）造成影響。 因此可以采用一種做法： 遍歷一次，每一步同時修改兩個節點就好了，這樣就可以規避上面兩個問題。 ## 關鍵點解析 - 用虛擬節點來簡化操作 - 循環的結束條件設置為 `odd && odd.next && even && even.next`, 不應該是`odd && even`, 否則需要記錄一下奇數節點的最后一個節點，復雜了操作 ## 代碼 - 語言支持：JS，C++ JavaScript Code: ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=328 lang=javascript * * [328] Odd Even Linked List * * */</span> <span class="hljs-title">/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */</span> <span class="hljs-title">/** * @param {ListNode} head * @return {ListNode} */</span> <span class="hljs-keyword">var</span> oddEvenList = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">head</span>) </span>{ <span class="hljs-keyword">if</span> (!head || !head.next) <span class="hljs-keyword">return</span> head; <span class="hljs-keyword">const</span> dummyHead1 = { next: head }; <span class="hljs-keyword">const</span> dummyHead2 = { next: head.next }; <span class="hljs-keyword">let</span> odd = dummyHead1.next; <span class="hljs-keyword">let</span> even = dummyHead2.next; <span class="hljs-keyword">while</span> (odd && odd.next && even && even.next) { <span class="hljs-keyword">const</span> oddNext = odd.next.next; <span class="hljs-keyword">const</span> evenNext = even.next.next; odd.next = oddNext; even.next = evenNext; odd = oddNext; even = evenNext; } odd.next = dummyHead2.next; <span class="hljs-keyword">return</span> dummyHead1.next; }; ``` ``` C++ Code： ``` <pre class="calibre18">``` <span class="hljs-title">/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */</span> <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-function">ListNode* <span class="hljs-title">oddEvenList</span><span class="hljs-params">(ListNode* head)</span> </span>{ <span class="hljs-keyword">if</span> (head == <span class="hljs-params">nullptr</span>) <span class="hljs-keyword">return</span> head; <span class="hljs-keyword">auto</span> odd = head, evenHead = head->next, even = head->next; <span class="hljs-title">// 因為“每次循環之后依然保持odd在even之前”，循環條件可以只判斷even和even->next是否為空，修改odd和even的指向的操作也可以簡化</span> <span class="hljs-keyword">while</span> (even != <span class="hljs-params">nullptr</span> && even->next != <span class="hljs-params">nullptr</span>) { odd->next = even->next; odd = odd->next; even->next = odd->next; even = even->next; } odd->next = evenHead; <span class="hljs-keyword">return</span> head; } }; ``` ``` **復雜度分析** - 時間復雜度：O(N)O(N)O(N) - 空間復雜度：O(1)O(1)O(1) 大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。