<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>

                合規國際互聯網加速 OSASE為企業客戶提供高速穩定SD-WAN國際加速解決方案。 廣告
                # 0025. K 個一組翻轉鏈表 ## 題目地址(25. K 個一組翻轉鏈表) <https://leetcode-cn.com/problems/reverse-nodes-in-k-group/> ## 題目描述 ``` <pre class="calibre18">``` 給你一個鏈表,每 k 個節點一組進行翻轉,請你返回翻轉后的鏈表。 k 是一個正整數,它的值小于或等于鏈表的長度。 如果節點總數不是 k 的整數倍,那么請將最后剩余的節點保持原有順序。 示例: 給你這個鏈表:1->2->3->4->5 當 k = 2 時,應當返回: 2->1->4->3->5 當 k = 3 時,應當返回: 3->2->1->4->5 說明: 你的算法只能使用常數的額外空間。 你不能只是單純的改變節點內部的值,而是需要實際進行節點交換。 ``` ``` ## 前置知識 - 鏈表 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 題意是以 `k` 個 nodes 為一組進行翻轉,返回翻轉后的`linked list`. 從左往右掃描一遍`linked list`,掃描過程中,以 k 為單位把數組分成若干段,對每一段進行翻轉。給定首尾 nodes,如何對鏈表進行翻轉。 鏈表的翻轉過程,初始化一個為`null`的 `previous node(prev)`,然后遍歷鏈表的同時,當前`node (curr)`的下一個(next)指向前一個`node(prev)`, 在改變當前 node 的指向之前,用一個臨時變量記錄當前 node 的下一個`node(curr.next)`. 即 ``` <pre class="calibre18">``` ListNode temp = curr.next; curr.next = prev; prev = curr; curr = temp; ``` ``` 舉例如圖:翻轉整個鏈表 `1->2->3->4->null` -> `4->3->2->1->null` ![](https://img.kancloud.cn/5d/56/5d56d16214e034a468f561eb6c5733d9_1440x1080.jpg) 這里是對每一組(`k個nodes`)進行翻轉, 1. 先分組,用一個`count`變量記錄當前節點的個數 2. 用一個`start` 變量記錄當前分組的起始節點位置的前一個節點 3. 用一個`end`變量記錄要翻轉的最后一個節點位置 4. 翻轉一組(`k個nodes`)即`(start, end) - start and end exclusively`。 5. 翻轉后,`start`指向翻轉后鏈表, 區間`(start,end)`中的最后一個節點, 返回`start` 節點。 6. 如果不需要翻轉,`end` 就往后移動一個(`end=end.next`),每一次移動,都要`count+1`. 如圖所示 步驟 4 和 5: 翻轉區間鏈表區間`(start, end)` ![](https://img.kancloud.cn/55/1a/551afe14f06290978156c7a612b4d4e9_1273x969.jpg) 舉例如圖,`head=[1,2,3,4,5,6,7,8], k = 3` ![](https://img.kancloud.cn/27/63/27633cc6347f53638a7e94a83b4b86e3_1398x1080.jpg) > **NOTE**: 一般情況下對鏈表的操作,都有可能會引入一個新的`dummy node`,因為`head`有可能會改變。這里`head 從1->3`, `dummy (List(0))`保持不變。 #### 復雜度分析 - *時間復雜度:*`O(n) - n is number of Linked List` - *空間復雜度:*`O(1)` ## 關鍵點分析 1. 創建一個 dummy node 2. 對鏈表以 k 為單位進行分組,記錄每一組的起始和最后節點位置 3. 對每一組進行翻轉,更換起始和最后的位置 4. 返回`dummy.next`. ## 代碼 (`Java/Python3/javascript`) *Java Code* ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">ReverseKGroupsLinkedList</span> </span>{ <span class="hljs-function"><span class="hljs-keyword">public</span> ListNode <span class="hljs-title">reverseKGroup</span><span class="hljs-params">(ListNode head, <span class="hljs-keyword">int</span> k)</span> </span>{ <span class="hljs-keyword">if</span> (head == <span class="hljs-keyword">null</span> || k == <span class="hljs-params">1</span>) { <span class="hljs-keyword">return</span> head; } ListNode dummy = <span class="hljs-keyword">new</span> ListNode(<span class="hljs-params">0</span>); dummy.next = head; ListNode start = dummy; ListNode end = head; <span class="hljs-keyword">int</span> count = <span class="hljs-params">0</span>; <span class="hljs-keyword">while</span> (end != <span class="hljs-keyword">null</span>) { count++; <span class="hljs-title">// group</span> <span class="hljs-keyword">if</span> (count % k == <span class="hljs-params">0</span>) { <span class="hljs-title">// reverse linked list (start, end]</span> start = reverse(start, end.next); end = start.next; } <span class="hljs-keyword">else</span> { end = end.next; } } <span class="hljs-keyword">return</span> dummy.next; } <span class="hljs-title">/** * reverse linked list from range (start, end), return last node. * for example: * 0->1->2->3->4->5->6->7->8 * | | * start end * * After call start = reverse(start, end) * * 0->3->2->1->4->5->6->7->8 * | | * start end * first * */</span> <span class="hljs-function"><span class="hljs-keyword">private</span> ListNode <span class="hljs-title">reverse</span><span class="hljs-params">(ListNode start, ListNode end)</span> </span>{ ListNode curr = start.next; ListNode prev = start; ListNode first = curr; <span class="hljs-keyword">while</span> (curr != end){ ListNode temp = curr.next; curr.next = prev; prev = curr; curr = temp; } start.next = prev; first.next = curr; <span class="hljs-keyword">return</span> first; } } ``` ``` *Python3 Cose* ``` <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">reverseKGroup</span><span class="hljs-params">(self, head: ListNode, k: int)</span> -> ListNode:</span> <span class="hljs-keyword">if</span> head <span class="hljs-keyword">is</span> <span class="hljs-keyword">None</span> <span class="hljs-keyword">or</span> k < <span class="hljs-params">2</span>: <span class="hljs-keyword">return</span> head dummy = ListNode(<span class="hljs-params">0</span>) dummy.next = head start = dummy end = head count = <span class="hljs-params">0</span> <span class="hljs-keyword">while</span> end: count += <span class="hljs-params">1</span> <span class="hljs-keyword">if</span> count % k == <span class="hljs-params">0</span>: start = self.reverse(start, end.next) <span class="hljs-title"># end 調到下一個</span> end = start.next <span class="hljs-keyword">else</span>: end = end.next <span class="hljs-keyword">return</span> dummy.next <span class="hljs-title"># (start, end) 左右都開放</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">reverse</span><span class="hljs-params">(self, start, end)</span>:</span> prev, curr = start, start.next first = curr <span class="hljs-title"># 反轉</span> <span class="hljs-keyword">while</span> curr != end: next = curr.next curr.next = prev prev = curr curr = next <span class="hljs-title"># 將反轉后的鏈表添加到原鏈表中</span> start.next = prev first.next = end <span class="hljs-title"># 返回反轉前的頭, 也就是反轉后的尾部</span> <span class="hljs-keyword">return</span> first ``` ``` *javascript code* ``` <pre class="calibre18">``` <span class="hljs-title">/** * @param {ListNode} head * @param {number} k * @return {ListNode} */</span> <span class="hljs-keyword">var</span> reverseKGroup = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">head, k</span>) </span>{ <span class="hljs-title">// 標兵</span> <span class="hljs-keyword">let</span> dummy = <span class="hljs-keyword">new</span> ListNode(); dummy.next = head; <span class="hljs-keyword">let</span> [start, end] = [dummy, dummy.next]; <span class="hljs-keyword">let</span> count = <span class="hljs-params">0</span>; <span class="hljs-keyword">while</span> (end) { count++; <span class="hljs-keyword">if</span> (count % k === <span class="hljs-params">0</span>) { start = reverseList(start, end.next); end = start.next; } <span class="hljs-keyword">else</span> { end = end.next; } } <span class="hljs-keyword">return</span> dummy.next; <span class="hljs-title">// 翻轉stat -> end的鏈表</span> <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">reverseList</span>(<span class="hljs-params">start, end</span>) </span>{ <span class="hljs-keyword">let</span> [pre, cur] = [start, start.next]; <span class="hljs-keyword">const</span> first = cur; <span class="hljs-keyword">while</span> (cur !== end) { <span class="hljs-keyword">let</span> next = cur.next; cur.next = pre; pre = cur; cur = next; } start.next = pre; first.next = cur; <span class="hljs-keyword">return</span> first; } }; ``` ``` ## 參考(References) - [Leetcode Discussion (yellowstone)](https://leetcode.com/problems/reverse-nodes-in-k-group/discuss/11440/Non-recursive-Java-solution-and-idea) ## 擴展 1 - 要求從后往前以`k`個為一組進行翻轉。**(字節跳動(ByteDance)面試題)** 例子,`1->2->3->4->5->6->7->8, k = 3`, 從后往前以`k=3`為一組, - `6->7->8` 為一組翻轉為`8->7->6`, - `3->4->5`為一組翻轉為`5->4->3`. - `1->2`只有 2 個 nodes 少于`k=3`個,不翻轉。 最后返回: `1->2->5->4->3->8->7->6` 這里的思路跟從前往后以`k`個為一組進行翻轉類似,可以進行預處理: 1. 翻轉鏈表 2. 對翻轉后的鏈表進行從前往后以 k 為一組翻轉。 3. 翻轉步驟 2 中得到的鏈表。 例子:`1->2->3->4->5->6->7->8, k = 3` 1. 翻轉鏈表得到:`8->7->6->5->4->3->2->1` 2. 以 k 為一組翻轉: `6->7->8->3->4->5->2->1` 3. 翻轉步驟#2 鏈表: `1->2->5->4->3->8->7->6` ## 擴展 2 如果這道題你按照 [92.reverse-linked-list-ii](92.reverse-linked-list-ii.html) 提到的 `p1, p2, p3, p4`(四點法) 的思路來思考的話會很清晰。 代碼如下(Python): ``` <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">reverseKGroup</span><span class="hljs-params">(self, head: ListNode, k: int)</span> -> ListNode:</span> <span class="hljs-keyword">if</span> head <span class="hljs-keyword">is</span> <span class="hljs-keyword">None</span> <span class="hljs-keyword">or</span> k < <span class="hljs-params">2</span>: <span class="hljs-keyword">return</span> head dummy = ListNode(<span class="hljs-params">0</span>) dummy.next = head pre = dummy cur = head count = <span class="hljs-params">0</span> <span class="hljs-keyword">while</span> cur: count += <span class="hljs-params">1</span> <span class="hljs-keyword">if</span> count % k == <span class="hljs-params">0</span>: pre = self.reverse(pre, cur.next) <span class="hljs-title"># end 調到下一個位置</span> cur = pre.next <span class="hljs-keyword">else</span>: cur = cur.next <span class="hljs-keyword">return</span> dummy.next <span class="hljs-title"># (p1, p4) 左右都開放</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">reverse</span><span class="hljs-params">(self, p1, p4)</span>:</span> prev, curr = p1, p1.next p2 = curr <span class="hljs-title"># 反轉</span> <span class="hljs-keyword">while</span> curr != p4: next = curr.next curr.next = prev prev = curr curr = next <span class="hljs-title"># 將反轉后的鏈表添加到原鏈表中</span> <span class="hljs-title"># prev 相當于 p3</span> p1.next = prev p2.next = p4 <span class="hljs-title"># 返回反轉前的頭, 也就是反轉后的尾部</span> <span class="hljs-keyword">return</span> p2 <span class="hljs-title"># @lc code=end</span> ``` ``` **復雜度分析** - 時間復雜度:O(N)O(N)O(N) - 空間復雜度:O(1)O(1)O(1) ## 相關題目 - [92.reverse-linked-list-ii](92.reverse-linked-list-ii.html) - [206.reverse-linked-list](206.reverse-linked-list.html) 大家對此有何看法,歡迎給我留言,我有時間都會一一查看回答。更多算法套路可以訪問我的 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>

                              哎呀哎呀视频在线观看