前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【综合笔试题】难度 2/5,说难不难的翻转链表题

【综合笔试题】难度 2/5,说难不难的翻转链表题

作者头像
宫水三叶的刷题日记
发布2021-06-23 10:48:35
5260
发布2021-06-23 10:48:35
举报

题目描述

这是 LeetCode 上的 「25. K 个一组翻转链表」 ,难度为 「困难」

给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。

k 是一个正整数,它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

进阶:

  • 你可以设计一个只使用常数额外空间的算法来解决此问题吗?
  • 你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。

示例 1:

代码语言:javascript
复制
输入:head = [1,2,3,4,5], k = 2

输出:[2,1,4,3,5]

示例 2:

代码语言:javascript
复制
输入:head = [1,2,3,4,5], k = 3

输出:[3,2,1,4,5]

示例 3:

代码语言:javascript
复制
输入:head = [1,2,3,4,5], k = 1

输出:[1,2,3,4,5]

示例 4:

代码语言:javascript
复制
输入:head = [1], k = 1

输出:[1]

提示:

  • 列表中节点的数量在范围 sz 内
  • 1 <= sz <= 5000
  • 0 <= Node.val <= 1000
  • 1 <= k <= sz

迭代解法(哨兵技巧)

哨兵技巧我们在前面的多道链表题讲过,让三叶来帮你回忆一下:

做有关链表的题目,有个常用技巧:添加一个虚拟头结点(哨兵),帮助简化边界情况的判断。

链表和树的题目天然适合使用递归来做。

但这次我们先将简单的「递归版本」放一放,先搞清楚迭代版本该如何实现。

我们可以设计一个翻转函数 reverse

传入节点 root 作为参数,函数的作用是将以 root 为起点的

k

个节点进行翻转。

当以 root 为起点的长度为

k

的一段翻转完成后,再将下一个起始节点传入,直到整条链表都被处理完成。

当然,在 reverse 函数真正执行翻转前,需要先确保节点 root 后面至少有

k

个节点。

我们可以结合图解再来体会一下这个过程:

假设当前样例为 1->2->3->4->5->6->7k = 3

然后我们调用 reverse(cur, k),在 reverse() 方法内部,几个指针的指向如图所示,会通过先判断 cur 是否为空,从而确定是否有足够的节点进行翻转:

然后先通过 while 循环,将中间的数量为 k - 1 的 next 指针进行翻转:

最后再处理一下局部的头结点和尾结点,这样一次 reverse(cur, k) 执行就结束了:

回到主方法,将 cur 往前移动 k 步,再调用 reverse(cur, k) 实现 k 个一组翻转:

代码:

代码语言:javascript
复制
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode cur = dummy;
        while (cur != null) {
            reverse(cur, k);
            int u = k;    
            while (u-- > 0 && cur != null) cur = cur.next;
        }
        return dummy.next;
    }
    // reverse 的作用是将 root 后面的 k 个节点进行翻转
    void reverse(ListNode root, int k) {
        // 检查 root 后面是否有 k 个节点
        int u = k;
        ListNode cur = root;
        while (u-- > 0 && cur != null) cur = cur.next;
        if (cur == null) return;

        // 进行翻转
        ListNode tail = cur.next;
        ListNode a = root.next, b = a.next;
        // 当需要翻转 k 个节点时,中间就有 k - 1 个 next 指针需要翻转
        while (k-- > 1) {
            ListNode c = b.next;
            b.next = a;
            a = b;
            b = c;
        }
        root.next.next = tail;
        root.next = a;
    }
}
  • 时间复杂度:会将每个节点处理一遍。复杂度为
O(n)
  • 空间复杂度:
O(1)

递归解法

搞懂了较难的「迭代哨兵」版本之后,常规的「递归无哨兵」版本写起来应该更加容易了。

需要注意的是,当我们不使用「哨兵」时,检查是否足够

k

位,只需要检查是否有

k - 1

next

指针即可。

代码:

代码语言:javascript
复制
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        int u = k;
        ListNode p = head;
        while (p != null && u-- > 1) p = p.next;
        if (p == null) return head;

        ListNode tail = head;
        ListNode prev = head, cur = prev.next;
        u = k;
        while (u-- > 1) {
            ListNode tmp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = tmp;
        }
        tail.next = reverseKGroup(cur, k);
        return prev;
    }
}
  • 时间复杂度:会将每个节点处理一遍。复杂度为
O(n)
  • 空间复杂度:只有忽略递归带来的空间开销才是
O(1)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.25 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode。

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-05-17,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 宫水三叶的刷题日记 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述
  • 迭代解法(哨兵技巧)
  • 递归解法
  • 最后
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档