> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/5.linkedlist/450reverse-nodes-in-k-group.md). # 25.Reverse Nodes in k-Group (H) ## 1.Description(Hard) Given a linked list, reverse the nodes of a linked list k at a time and return its modified list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is. You may not alter the values in the nodes, only nodes itself may be changed.\ Only constant memory is allowed. **Example** Given this linked list:`1->2->3->4->5` For k = 2, you should return:`2->1->4->3->5` For k = 3, you should return:`3->2->1->4->5` ## 2.Code **Version 1: Non-Recursive** 每K个元素，翻转一次。最后一次如果不到K，再翻转回来即可。 几乎用到linked list题所有的技巧。 1. p指针总是指向每次要反转的k个节点的前一个节点。因为反转后仍然要接回这个节点之后。 2. ln8：如果p指针后没有节点或只剩一个节点了，那么整个反转结束。 3. ln11-17：尝试反转k个节点，如果遇到尾部，则提前结束。i记录了反转多少次。注意，要反转k个节点的话，实际反转指针只需要k-1次。 4. ln19-24：如果成功反转k个节点，则i=k-1。此时将反转的k个节点两头接回，并将p移动到反转后k个节点的最后一个节点处，以备继续反转之后的k个节点。 5. ln25-35：如果没能反转k个节点就遇到尾部。则逆向还原。 ``` /*就是区间的reverse。因为题目要求的是k group逆转嘛。注意人返回的是最后一个(last)节点， * 这样下一个k-group就可以用上了。牛人的想法真是周到体贴～～。 * 主方法里面，遍历的过程中每次都计数，每次到达k个节点，就可以使用pre和head.next调用上面的方法逆转了. */ public ListNode reverseKGroup(ListNode head, int k) { if(head==null || k==1){ return head; } ListNode dummy=new ListNode(0); dummy.next=head; ListNode pre=dummy; int i=0; while(head!=null){ i++; if(i%k==0){ pre=reverse(pre,head.next); head=pre.next; //the first element in next k element } else{ head=head.next; } } return dummy.next; } /** * Reverse a link list between pre and next exclusively * an example: * a linked list: * 0->1->2->3->4->5->6 * | | * pre next * after call pre = reverse(pre, next) * * 0->3->2->1->4->5->6 * | | * pre next * @param pre * @param next * @return the reversed list's last node, which is the precedence of parameter next */ //保持一个invariant就是last节点始终在最后（cur的前面一个） public ListNode reverse(ListNode pre,ListNode end){ ListNode last=pre.next; ListNode current=last.next; while(current!=end){ last.next=current.next; current.next=pre.next; pre.next=current; current=last.next; } return last; } ``` **Version 2: Recursive** [**https://labuladong.github.io/algo/2/17/18/**](https://labuladong.github.io/algo/2/17/18/)\ 首先，前文 [学习数据结构的框架思维](https://labuladong.github.io/algo/1/2/)提到过，链表是一种兼具递归和迭代性质的数据结构，认真思考一下可以发现**这个问题具有递归性质**。 什么叫递归性质？直接上图理解，比如说我们对这个链表调用 `reverseKGroup(head, 2)`，即以 2 个节点为一组反转链表： [![](https://labuladong.github.io/algo/images/kgroup/1.jpg)](https://labuladong.github.io/algo/images/kgroup/1.jpg) 如果我设法把前 2 个节点反转，那么后面的那些节点怎么处理？后面的这些节点也是一条链表，而且规模（长度）比原来这条链表小，这就叫**子问题**。 [![](https://labuladong.github.io/algo/images/kgroup/2.jpg)](https://labuladong.github.io/algo/images/kgroup/2.jpg) 我们可以直接递归调用 `reverseKGroup(cur, 2)`，因为子问题和原问题的结构完全相同，这就是所谓的递归性质。 发现了递归性质，就可以得到大致的算法流程： **1、先反转以 `head` 开头的 `k` 个元素**。 [![](https://labuladong.github.io/algo/images/kgroup/3.jpg)](https://labuladong.github.io/algo/images/kgroup/3.jpg) **2、将第 `k + 1` 个元素作为 `head` 递归调用 `reverseKGroup` 函数**。 [![](https://labuladong.github.io/algo/images/kgroup/4.jpg)](https://labuladong.github.io/algo/images/kgroup/4.jpg) **3、将上述两个过程的结果连接起来**。 [![](https://labuladong.github.io/algo/images/kgroup/5.jpg)](https://labuladong.github.io/algo/images/kgroup/5.jpg) 整体思路就是这样了，最后一点值得注意的是，递归函数都有个 base case，对于这个问题是什么呢？ 题目说了，如果最后的元素不足 `k` 个，就保持不变。这就是 base case，待会会在代码里体现。 #### 二、代码实现 首先，我们要实现一个 `reverse` 函数反转一个区间之内的元素。在此之前我们再简化一下，给定链表头结点，如何反转整个链表？ ```java // 反转以 a 为头结点的链表 ListNode reverse(ListNode a) { ListNode pre, cur, nxt; pre = null; cur = a; nxt = a; while (cur != null) { nxt = cur.next; // 逐个结点反转 cur.next = pre; // 更新指针位置 pre = cur; cur = nxt; } // 返回反转后的头结点 return pre; } ``` [![](https://labuladong.github.io/algo/images/kgroup/8.gif)](https://labuladong.github.io/algo/images/kgroup/8.gif) 这次使用迭代思路来实现的，借助动画理解应该很容易。 「反转以 `a` 为头结点的链表」其实就是「反转 `a` 到 null 之间的结点」，那么如果让你「反转 `a` 到 `b` 之间的结点」，你会不会？ 只要更改函数签名，并把上面的代码中 `null` 改成 `b` 即可： ```java /** 反转区间 [a, b) 的元素，注意是左闭右开 */ ListNode reverse(ListNode a, ListNode b) { ListNode pre, cur, nxt; pre = null; cur = a; nxt = a; // while 终止的条件改一下就行了 while (cur != b) { nxt = cur.next; cur.next = pre; pre = cur; cur = nxt; } // 返回反转后的头结点 return pre; } ``` 现在我们迭代实现了反转部分链表的功能，接下来就按照之前的逻辑编写 `reverseKGroup` 函数即可： ```java ListNode reverseKGroup(ListNode head, int k) { if (head == null) return null; // 区间 [a, b) 包含 k 个待反转元素 ListNode a, b; a = b = head; for (int i = 0; i < k; i++) { // 不足 k 个，不需要反转，base case if (b == null) return head; b = b.next; } // 反转前 k 个元素 ListNode newHead = reverse(a, b); // 递归反转后续链表并连接起来 a.next = reverseKGroup(b, k); return newHead; } ``` 解释一下 `for` 循环之后的几句代码，注意 `reverse` 函数是反转区间 `[a, b)`，所以情形是这样的： [![](https://labuladong.github.io/algo/images/kgroup/6.jpg)](https://labuladong.github.io/algo/images/kgroup/6.jpg) 递归部分就不展开了，整个函数递归完成之后就是这个结果，完全符合题意： [![](https://labuladong.github.io/algo/images/kgroup/7.jpg)](https://labuladong.github.io/algo/images/kgroup/7.jpg) #### 三、最后说两句 从阅读量上看，基本数据结构相关的算法文章看的人都不多，我想说这是要吃亏的。 大家喜欢看动态规划相关的问题，可能因为面试很常见，但就我个人理解，很多算法思想都是源于数据结构的。我们公众号的成名之作之一，「学习数据结构的框架思维」就提过，什么动规、回溯、分治算法，其实都是树的遍历，树这种结构它不就是个多叉链表吗？你能处理基本数据结构的问题，解决一般的算法问题应该也不会太费事。 那么如何分解问题、发现递归性质呢？这个只能多练习，也许后续可以专门写一篇文章来探讨一下，本文就到此为止吧，希望对大家有帮助！