旋转链表 :「快慢指针」&「闭合成环」解法|Java 刷题打卡

简介: 旋转链表 :「快慢指针」&「闭合成环」解法|Java 刷题打卡

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


题目描述



这是 LeetCode 上的 61. 旋转链表 ,难度为 中等


Tag : 「链表」、[快慢指针]


给你一个链表的头节点 head ,旋转链表,将链表每个节点向右移动 k 个位置。


示例 1:

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


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



示例 2:

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


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


提示:


  • 链表中节点的数目在范围 [0, 500] 内
  • -100 <= Node.val <= 100
  • 0 <= k <= 2 * 10^9109


快慢指针



本质还是道模拟题,分步骤处理即可:


  • 避免不必要的旋转:与链表长度成整数倍的「旋转」都是没有意义的(旋转前后链表不变)
  • 使用「快慢指针」找到倒数第 k 个节点(新头结点),然后完成基本的链接与断开与断开操作


代码(感谢 @Die Eule 同学提供的 cpp 和 js 版本):


class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || k == 0) return head;
        // 计算有效的 k 值:对于与链表长度成整数倍的「旋转」都是没有意义的(旋转前后链表不变)
        int tot = 0;
        ListNode tmp = head;
        while (tmp != null && ++tot > 0) tmp = tmp.next;
        k %= tot;
        if (k == 0) return head;
        // 使用「快慢指针」找到倒数第 k 个节点(新头结点):slow 会停在「新头结点」的「前一位」,也就是「新尾结点」
        ListNode slow = head, fast = head;
        while (k-- > 0) fast = fast.next;
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        // 保存新头结点,并将新尾结点的 next 指针置空
        ListNode nHead = slow.next;
        slow.next = null;
        // 将新链表的前半部分(原链表的后半部分)与原链表的头结点链接上
        fast.next = head;
        return nHead;
    }
}
复制代码


  • 时间复杂度:O(n)O(n)
  • 空间复杂度:O(1)O(1)


闭合成环



另外一个做法是,先成环,再断开:


  • 找到原链表的最后一个节点,将其与原链表的头结点相连(成环),并统计链表长度,更新有效 k 值
  • 从原链表的头节点出发,找到需要断开的点,进行断开


代码:


class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || k == 0) return head;
        // 先将链表成环,并记录链表的长度
        // tmp 会记录住原链表最后一位节点
        int tot = 0;
        ListNode tmp = head;
        while (tmp.next != null && ++tot > 0) tmp = tmp.next;
        tot++;
        k %= tot;
        if (k == 0) return head;
        // 正式成环
        tmp.next = head;
        // 从原链表 head 出发,走 tot - k - 1 步,找到「新尾结点」进行断开,并将其下一个节点作为新节点返回
        k = tot - k - 1;
        while (k-- > 0) head = head.next;
        ListNode nHead = head.next;
        head.next = null;
        return nHead;
    }
}
复制代码


  • 时间复杂度:O(n)O(n)
  • 空间复杂度:O(1)O(1)


最后



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


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


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


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

相关文章
|
11月前
|
Java 编译器 程序员
Java面试高频题:用最优解法算出2乘以8!
本文探讨了面试中一个看似简单的数学问题——如何高效计算2×8。从直接使用乘法、位运算优化、编译器优化、加法实现到大整数场景下的处理,全面解析了不同方法的原理和适用场景,帮助读者深入理解计算效率优化的重要性。
176 6
|
11月前
|
算法 索引
单链表题+数组题(快慢指针和左右指针)
单链表题+数组题(快慢指针和左右指针)
107 1
|
存储 Java 开发者
揭秘!HashMap底层结构大起底:从数组到链表,再到红黑树,Java性能优化的秘密武器!
【8月更文挑战第24天】HashMap是Java集合框架中的核心组件,以其高效的键值对存储和快速访问能力广受开发者欢迎。在JDK 1.8及以后版本中,HashMap采用了数组+链表+红黑树的混合结构,实现了高性能的同时解决了哈希冲突问题。数组作为基石确保了快速定位;链表则用于处理哈希冲突;而当链表长度达到一定阈值时,通过转换为红黑树进一步提升性能。此外,HashMap还具备动态扩容机制,当负载因子超过预设值时自动扩大容量并重新哈希,确保整体性能。通过对HashMap底层结构的深入了解,我们可以更好地利用其优势解决实际开发中的问题。
311 0
|
人工智能 算法 Java
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
158 1
|
存储 算法 Java
LeetCode经典算法题:预测赢家+香槟塔java解法
LeetCode经典算法题:预测赢家+香槟塔java解法
174 1
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
152 6
|
算法 Java
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
145 0
|
存储 算法 Java
LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
141 0
|
存储 算法 Java
LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
116 0
HashTab基于链表简单实现(java,不包含扩容)
HashTab基于链表简单实现(java,不包含扩容)

热门文章

最新文章