<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ThinkChat2.0新版上線,更智能更精彩,支持會話、畫圖、視頻、閱讀、搜索等,送10W Token,即刻開啟你的AI之旅 廣告
                # 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 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看