# 0025. K 个一组翻转链表 ### 题目地址(25. K 个一组翻转链表) ### 题目描述 ``` 给你一个链表，每 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)`. 即 ``` ListNode temp = curr.next; curr.next = prev; prev = curr; curr = temp; ``` 举例如图：翻转整个链表 `1->2->3->4->null` -> `4->3->2->1->null` ![reverse linked list](https://p.ipic.vip/qulz9a.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）` ![reverse linked list range in (start, end)](https://p.ipic.vip/5cga6g.jpg) 举例如图，`head=[1,2,3,4,5,6,7,8], k = 3` ![reverse k nodes in linked list](https://p.ipic.vip/7whudf.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* ```java 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* ```python class Solution: # 翻转一个子链表，并且返回新的头与尾 def reverse(self, head: ListNode, tail: ListNode, terminal): cur = head pre = None while cur != terminal: next = cur.next cur.next = pre pre = cur cur = next return tail, head def reverseKGroup(self, head: ListNode, k: int) -> ListNode: ans = ListNode() ans.next = head pre = ans while head: tail = pre # 查看剩余部分长度是否大于等于 k for i in range(k): tail = tail.next if not tail: return ans.next next = tail.next head, tail = self.reverse(head, tail, tail.next) # 把子链表重新接回原链表 pre.next = head tail.next = next pre = tail head = next return ans.next ``` *javascript code* ```js /** * @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](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/92.reverse-linked-list-ii) 提到的 `p1, p2, p3, p4`（四点法） 的思路来思考的话会很清晰。 代码如下（Python）： ```py 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(1)$ ### 相关题目 * [92.reverse-linked-list-ii](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/92.reverse-linked-list-ii) * [206.reverse-linked-list](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/easy/206.reverse-linked-list) 大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 ![](https://p.ipic.vip/urt7jp.jpg)