旋转链表 :「快慢指针」&「闭合成环」解法|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 原题链接和其他优选题解。

相关文章
|
3月前
【bug记录】旋转链表与力扣报错:member access within null pointer of type ‘struct ListNode‘
【bug记录】旋转链表与力扣报错:member access within null pointer of type ‘struct ListNode‘
|
18天前
|
算法 索引
单链表题+数组题(快慢指针和左右指针)
单链表题+数组题(快慢指针和左右指针)
24 1
|
5月前
|
Java
环形数组链表(java)
环形数组链表(java)
|
3月前
|
存储 Java 开发者
揭秘!HashMap底层结构大起底:从数组到链表,再到红黑树,Java性能优化的秘密武器!
【8月更文挑战第24天】HashMap是Java集合框架中的核心组件,以其高效的键值对存储和快速访问能力广受开发者欢迎。在JDK 1.8及以后版本中,HashMap采用了数组+链表+红黑树的混合结构,实现了高性能的同时解决了哈希冲突问题。数组作为基石确保了快速定位;链表则用于处理哈希冲突;而当链表长度达到一定阈值时,通过转换为红黑树进一步提升性能。此外,HashMap还具备动态扩容机制,当负载因子超过预设值时自动扩大容量并重新哈希,确保整体性能。通过对HashMap底层结构的深入了解,我们可以更好地利用其优势解决实际开发中的问题。
100 0
|
3月前
|
算法 Java
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
LeetCode初级算法题:环形链表+排列硬币+合并两个有序数组java解法
54 0
|
3月前
|
存储 算法 Java
LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
44 0
|
6月前
|
数据采集 Java 数据处理
Java流与链表:探索java.util.stream与LinkedList的交汇点
本文探讨了Java中流(Streams)与链表(LinkedList)的结合使用,展示了如何通过流处理LinkedList以实现高效数据操作。示例代码包括LinkedList的基本操作、使用Stream进行过滤和映射,以及结合HttpClient和代理IP实现网络爬虫。代理IP有助于绕过反爬机制,提高爬取效率。通过结合这些技术,开发者能编写出更简洁、高效的代码。
Java流与链表:探索java.util.stream与LinkedList的交汇点
|
5月前
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
48 2
|
5月前
|
算法 Java C语言
【经典算法】LeetCode25:K 个一组翻转链表(Java/C/Python3,Hard)
【经典算法】LeetCode25:K 个一组翻转链表(Java/C/Python3,Hard)
33 1
|
5月前
|
算法 安全 Java
【经典算法】LeetCode 21:合并两个有序链表Java/C/Python3实现含注释说明,Easy)
【经典算法】LeetCode 21:合并两个有序链表Java/C/Python3实现含注释说明,Easy)
35 1