递归 | K个一组反转链表

今天分享的内容是LeetCode #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=2为一组进行链表反转。因此，在除去前2个节点后，nextHead指向节点3。在经过reverseKGroup(nextHead,2)递归反转后，链表结构如下图所示。注意在这里，不要试图去在大脑中复现reverseKGroup这个递推公式的调用过程，只需知道其执行后的结果就可以了。

到此，我们完成了除去前2个节点之后，剩余节点的反转。接着要做的是反转前k=2个节点。反转后结果如下图所示：

这时，只需将head的后继指针指向变量subList所指向的节点，就完成了K个一组反转链表这个任务。

在加上反转链表中前k个节点的代码后，代码进一步完善如下： public ListNode reverseKGroup(ListNode head, int k) { // nextHead指向链表中除去k个节点之后的头节点 // 初始指向节点head ListNode nextHead = head; // 链表中剩余节点个数 int remainNum = 0; while (remainNum < k){ // 根据题意如果链表剩余节点个数不足k个 // 则不需要反转，因此直接返回head if (nextHead == null) { return head; } remainNum++; nextHead = nextHead.next; } // 递归反转链表中除去前k个节点的后续节点 ListNode subList = reverseKGroup(nextHead,k); // 反转链表中前k个节点 ListNode newHead = reverseTopN(head, k); // 前k个节点反转后，head指向的节点是反转后的链表中的最后一个节点 // 因此head指向的节点的后继指针指向subList head.next = subList; return newHead; } 最后我们看下如何反转链表中的前K个节点。动画演示如下： 反转前K=2个节点 反转前K个节点的代码实现如下: private ListNode reverseTopN(ListNode head, int n) { ListNode prev = null; // 当前考察的节点 ListNode cur = head; // num小于n，则表示当前节点需要反转 for(int num = 0; num < n; num++){ // 当前节点的下一个节点 ListNode next = cur.next; // 当前节点的后继指针指向prev cur.next = prev; // prev指向当前节点 // 表示其是next节点反转后的前一个节点 prev = cur; // cur指向下一个节点 // 表示下一个节点是待反转节点 cur = next; } return prev; } 今天的分享就到这里了 如有错误 欢迎在公众号后台留言指出 下一篇我们将学习新的内容，敬请期待