今天分享的内容是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; } 今天的分享就到这里了 如有错误 欢迎在公众号后台留言指出 下一篇我们将学习新的内容,敬请期待