0025. K 個一組翻轉鏈表 · ttttt

# 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">``` class ReverseKGroupsLinkedList { public ListNode reverseKGroup(ListNode head, int k) { if (head == null || k == 1) { return head; } ListNode dummy = new ListNode(0); dummy.next = head; ListNode start = dummy; ListNode end = head; int count = 0; while (end != null) { count++; // group if (count % k == 0) { // reverse linked list (start, end] start = reverse(start, end.next); end = start.next; } else { end = end.next; } } return dummy.next; } /** * 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 * */ private ListNode reverse(ListNode start, ListNode end) { ListNode curr = start.next; ListNode prev = start; ListNode first = curr; while (curr != end){ ListNode temp = curr.next; curr.next = prev; prev = curr; curr = temp; } start.next = prev; first.next = curr; return first; } } ``` ``` *Python3 Cose* ``` <pre class="calibre18">``` class Solution: def reverseKGroup(self, head: ListNode, k: int) -> ListNode: if head is None or k < 2: return head dummy = ListNode(0) dummy.next = head start = dummy end = head count = 0 while end: count += 1 if count % k == 0: start = self.reverse(start, end.next) # end 調到下一個 end = start.next else: end = end.next return dummy.next # (start, end）左右都開放 def reverse(self, start, end): prev, curr = start, start.next first = curr # 反轉 while curr != end: next = curr.next curr.next = prev prev = curr curr = next # 將反轉后的鏈表添加到原鏈表中 start.next = prev first.next = end # 返回反轉前的頭，也就是反轉后的尾部 return first ``` ``` *javascript code* ``` <pre class="calibre18">``` /** * @param {ListNode} head * @param {number} k * @return {ListNode} */ var reverseKGroup = function (head, k) { // 標兵 let dummy = new ListNode(); dummy.next = head; let [start, end] = [dummy, dummy.next]; let count = 0; while (end) { count++; if (count % k === 0) { start = reverseList(start, end.next); end = start.next; } else { end = end.next; } } return dummy.next; // 翻轉stat -> end的鏈表 function reverseList(start, end) { let [pre, cur] = [start, start.next]; const first = cur; while (cur !== end) { let next = cur.next; cur.next = pre; pre = cur; cur = next; } start.next = pre; first.next = cur; return 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">``` class Solution: def reverseKGroup(self, head: ListNode, k: int) -> ListNode: if head is None or k < 2: return head dummy = ListNode(0) dummy.next = head pre = dummy cur = head count = 0 while cur: count += 1 if count % k == 0: pre = self.reverse(pre, cur.next) # end 調到下一個位置 cur = pre.next else: cur = cur.next return dummy.next # (p1, p4）左右都開放 def reverse(self, p1, p4): prev, curr = p1, p1.next p2 = curr # 反轉 while curr != p4: next = curr.next curr.next = prev prev = curr curr = next # 將反轉后的鏈表添加到原鏈表中 # prev 相當于 p3 p1.next = prev p2.next = p4 # 返回反轉前的頭，也就是反轉后的尾部 return p2 # @lc code=end ``` ``` **復雜度分析** - 時間復雜度：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)