字节面试高频题(k 个一组翻转链表)|Java 刷题打卡

简介: 字节面试高频题(k 个一组翻转链表)|Java 刷题打卡

题目描述



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


Tag : 「递归」、「迭代」、「链表」


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


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


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


进阶:


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


示例 1:


网络异常,图片无法展示
|


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


示例 2:


网络异常,图片无法展示
|


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


示例 3:


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


示例 4:


输入:head = [1], k = 1
输出:[1]
复制代码


提示:


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


迭代解法(哨兵技巧)



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


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


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


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


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


传入节点 root 作为参数,函数的作用是将以 root 为起点的 kkk 个节点进行翻转。

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


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


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


假设当前样例为 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 个一组翻转:

网络异常,图片无法展示
|


代码:


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(n)O(n)
  • 空间复杂度:O(1)O(1)O(1)


递归解法



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


需要注意的是,当我们不使用「哨兵」时,检查是否足够 kkk 位,只需要检查是否有 k−1k - 1k1nextnextnext 指针即可。


代码:


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(n)O(n)
  • 空间复杂度:只有忽略递归带来的空间开销才是 O(1)O(1)O(1)


最后



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


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


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


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

相关文章
|
3月前
|
关系型数据库 MySQL Java
字节面试: MySQL 百万级 导入发生的 “死锁” 难题如何解决?“2序4拆”,彻底攻克
字节面试: MySQL 百万级 导入发生的 “死锁” 难题如何解决?“2序4拆”,彻底攻克
字节面试: MySQL 百万级 导入发生的 “死锁” 难题如何解决?“2序4拆”,彻底攻克
|
4月前
|
机器学习/深度学习 算法
24. 两两交换链表中的节点, 19.删除链表的倒数第N个节点 ,面试题 02.07. 链表相交
1. **两两交换链表中的节点**:通过引入虚拟头结点,使所有节点都能采用统一的交换逻辑,避免对头结点单独处理。 2. **删除链表的倒数第N个节点**:利用双指针技巧,让快慢指针保持N个节点的距离,当快指针到达末尾时,慢指针正好指向待删除节点的前一个节点。 3. **链表相交**:先计算两链表长度并调整起点,确保从相同距离末尾的位置开始遍历,从而高效找到相交节点或确定无交点。 以上方法均在时间复杂度和空间复杂度上进行了优化,适合用于理解和掌握链表的基本操作及常见算法设计思路。
|
9月前
|
人工智能 自然语言处理 架构师
字节面试: es怎么提升性能和精准度?(尼恩独家,史上最全)
本文由40岁老架构师尼恩撰写,针对ES(Elasticsearch)提升搜索性能和精准度的面试题进行详细解析。文章首先指出,提升ES速度和精准度是两个独立的问题,分别涉及性能优化和精准度优化。这些内容不仅有助于应对面试中的难题,还能帮助开发者在实际项目中构建更高效的搜索系统。尼恩强调,掌握这些知识后可以在面试中“吊打”面试官,轻松获得理想Offer。同时,他还提供了《尼恩Java面试宝典PDF》等资源供读者学习参考。
|
11月前
|
存储 算法 Java
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?
本文详解自旋锁的概念、优缺点、使用场景及Java实现。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?
|
11月前
|
存储 缓存 算法
面试官:单核 CPU 支持 Java 多线程吗?为什么?被问懵了!
本文介绍了多线程环境下的几个关键概念,包括时间片、超线程、上下文切换及其影响因素,以及线程调度的两种方式——抢占式调度和协同式调度。文章还讨论了减少上下文切换次数以提高多线程程序效率的方法,如无锁并发编程、使用CAS算法等,并提出了合理的线程数量配置策略,以平衡CPU利用率和线程切换开销。
面试官:单核 CPU 支持 Java 多线程吗?为什么?被问懵了!
|
11月前
|
NoSQL 中间件 Java
字节面试:聊聊 CAP 定理?哪些中间件是AP? 哪些是CP? 说说 为什么?
45岁老架构师尼恩在其读者交流群中分享了关于CAP定理的重要面试题及其解析,包括CAP定理的基本概念、CAP三要素之间的关系,以及如何在分布式系统设计中权衡一致性和可用性。文章还详细分析了几种常见中间件(如Redis Cluster、Zookeeper、MongoDB、Cassandra、Eureka、Nacos)的CAP特性,并提供了高端面试技巧,帮助读者在面试中脱颖而出。尼恩还推荐了其团队编写的《尼恩Java面试宝典PDF》等资料,助力求职者准备面试,提升技术水平。
|
12月前
|
Arthas Kubernetes Java
字节面试:CPU被打满了,CPU100%,如何处理?
尼恩,一位拥有20多年经验的老架构师,针对近期读者在一线互联网企业面试中遇到的CPU 100%和红包架构等问题,进行了系统化梳理。文章详细解析了CPU 100%的三大类型问题(业务类、并发类、内存类)及其九种常见场景,提供了使用jstack和arthas两大工具定位问题的具体步骤,并分享了解决死锁问题的实战案例。尼恩还强调了面试时应先考虑回滚版本,再使用工具定位问题的重要性。此外,尼恩提供了丰富的技术资料,如《尼恩Java面试宝典》等,帮助读者提升技术水平,轻松应对面试挑战。
字节面试:CPU被打满了,CPU100%,如何处理?
|
11月前
|
存储 缓存 Java
大厂面试必看!Java基本数据类型和包装类的那些坑
本文介绍了Java中的基本数据类型和包装类,包括整数类型、浮点数类型、字符类型和布尔类型。详细讲解了每种类型的特性和应用场景,并探讨了包装类的引入原因、装箱与拆箱机制以及缓存机制。最后总结了面试中常见的相关考点,帮助读者更好地理解和应对面试中的问题。
264 4
|
12月前
|
Java API 对象存储
JVM进阶调优系列(2)字节面试:JVM内存区域怎么划分,分别有什么用?
本文详细解析了JVM类加载过程的关键步骤,包括加载验证、准备、解析和初始化等阶段,并介绍了元数据区、程序计数器、虚拟机栈、堆内存及本地方法栈的作用。通过本文,读者可以深入了解JVM的工作原理,理解类加载器的类型及其机制,并掌握类加载过程中各阶段的具体操作。
|
12月前
|
算法 Java 数据中心
探讨面试常见问题雪花算法、时钟回拨问题,java中优雅的实现方式
【10月更文挑战第2天】在大数据量系统中,分布式ID生成是一个关键问题。为了保证在分布式环境下生成的ID唯一、有序且高效,业界提出了多种解决方案,其中雪花算法(Snowflake Algorithm)是一种广泛应用的分布式ID生成算法。本文将详细介绍雪花算法的原理、实现及其处理时钟回拨问题的方法,并提供Java代码示例。
1255 2

热门文章

最新文章