题目地址(25. K 个一组翻转链表)

https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

题目描述

  1. 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
  3. k 是一个正整数，它的值小于或等于链表的长度。
  5. 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
  7. 进阶：
  9. 你可以设计一个只使用常数额外空间的算法来解决此问题吗？
  10. 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
  14. 示例 1：
  16. 输入：head = [1,2,3,4,5], k = 2
  17. 输出：[2,1,4,3,5]
  20. 示例 2：
  22. 输入：head = [1,2,3,4,5], k = 3
  23. 输出：[3,2,1,4,5]
  26. 示例 3：
  28. 输入：head = [1,2,3,4,5], k = 1
  29. 输出：[1,2,3,4,5]
  32. 示例 4：
  34. 输入：head = [1], k = 1
  35. 输出：[1]
  38. 提示：
  40. 列表中节点的数量在范围 sz 内
  41. 1 <= sz <= 5000
  42. 0 <= Node.val <= 1000
  43. 1 <= k <= sz

前置知识


公司

  • 暂无

思路

第一道困难题 好像也不太难
使用递归的思想完成这道题
首先题目叫我们实现一个链表 每隔k个节点反转 我们在反转一组k个的节点的时候 剩余的节点同样可以这么做 这就把整个的问题拆分成了很多个子问题
image.png
如果我设法把前 2 个节点反转，那么后面的那些节点怎么处理？后面的这些节点也是一条链表，而且规模（长度）比原来这条链表小，这就叫子问题。
image.png
算法流程

  1. 先反转以 head 开头的 k 个元素。

image.png

  1. 将第 k + 1 个元素作为 head 递归调用 reverseKGroup 函数。
  2. 将上述两个过程的结果连接起来。

具体分析

  1. 之前做过的反转链表反转的是head节点到null节点 现在只需要将其中的null换成end节点就行
  2. 定义一个left和一个right节点 都指向head 然后判断剩余的节点是否满足k个 并且在这期间 将right节点移动到下一组的head节点
    然后反转left到right-1的节点 最后返回的是新的链表的头结点 然后用反转后的尾节点也就是left指向递归调用之后链表的结果

image.png
最后完成
image.png

关键点


代码

  • 语言支持：Java

Java Code:

  2. class Solution {
  3.     public ListNode reverseKGroup(ListNode head, int k) {
  4.         //递归中止条件
  5.         if (head == null) {
  6.             return null;
  7.         }
  8.         //定义要反转的链表的起始和结束位置
  9.         ListNode left , right;
  10.         left = right =head;
  11.         //判断剩余的链表长度是否大于k
  12.         for (int i = 0; i < k; i++) {
  13.             //超出链表的长度就不翻转了 直接返回剩余链表的头结点
  14.             if (right == null) {
  15.                 return head;
  16.             }
  17.             //如果不超出 此时right的位置在要反转的链表范围的下一个 刚好对应了下面方法里的cur != end
  18.             right = right.next;
  19.         }
  20.         //将head到 right上一个的元素反转 返回的值就是链表的头
  21.         ListNode reverse = reverse(left, right);
  22.         //因为反转了链表 原来为链表头的left反转后为链表的尾部 将链表的尾部和递归后的链表的头部相连
  23.         //递归返回的是right到剩余链表反转后的头部 将大问题分割为子问题
  24.         left.next = reverseKGroup(right, k);
  25.         return reverse;
  26.     }
  27.     //反转链表 原来的是反转 head -> null 现在是反转 head -> end
  28.     ListNode reverse(ListNode head, ListNode end) {
  29.         ListNode pre = null;
  30.         ListNode cur = head;
  31.         ListNode temp = head;
  32.         while (cur != end) {
  33.             temp = cur.next;
  34.             cur.next = pre;
  35.             pre = cur;
  36.             cur = temp;
  37.         }
  38.         return pre;
  39.     }
  40. }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：25. K 个一组翻转链表 - 图6#card=math&code=O%28n%29&id=zil3j)
  • 空间复杂度：25. K 个一组翻转链表 - 图7#card=math&code=O%28n%29&id=cQMsj)