LeetCode刷题--- 61. 旋转链表(快慢指针+闭合为环)

简介: LeetCode刷题--- 61. 旋转链表(快慢指针+闭合为环)



一、编程题: 61. 旋转链表(快慢指针+闭合为环)

1.题目描述

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

2.示例1:

输入:head = [1,2,3,4,5], k = 2

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

3.示例2:

输入:head = [0,1,2], k = 4

输出:[2,0,1]

4.提示:

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

二、解题思路

1. 方法1(快慢指针)

  这里使用快慢指针跟滑动窗口的思路是一样的,都是先找到倒数k+1个节点,然后在一起移动;

思路:
  • Step 1.创建快慢指针,遍历链表找到快指针位置(倒数第k+1个节点的);
  • Step 2.同时移动快慢指针直到快指针fast == null为止,此时慢指针指向新链表的尾节点(这里还要一个指针来记录快指针的前驱节点,这个要看移动情况来定用不用);
  • Step 3.对原链表进行拆分并返回新链表头节点即可;

看不懂解释的话,直接看算法图解比较容易理解点

复杂度分析:

时间复杂度:O(n)。

空间复杂度:O(1)。

算法图解

  找到快指针之后就同时移动快慢指针,红色部分代表着快指针,只有fast==null时才要记录其前驱节点fast_prev,为了后续链表拼接操作;(注:本人不会做成流程动画,希望会的朋友可以私信我指点一二,说个软件名字也可以,谢谢 🤩 🤩 🤩

2. 方法二:闭合为环

  假设链表的长度为n,可以发现这么规律,当向右移动次数k ≥ n时,只要移动k mod n次即可。而且每次n(或者n的倍数)次移动都是链表的原状态,所以推导出新链表的头节点位置为原链表的第n - (k mod n)个节点(从0开始计数);

思路:
  • Step 1.首先将链表够成环,遍历链表找到链表的尾节点,并计算出链表的长度list_length,然后将其与头节点相连(这里有个坑点,就是找链表尾节点的时候,循环终止条件是last.next != null,这里的计算出来的链表长度都要+1);
  • Step 2.由公式n-(k%n)可计算出新链表头节点在原链表的位置,根据该位置可以找到其前驱节点(也就是新链表的尾节点),当k为n的倍数时则不进行处理;
  • Step 3.找到新链表的尾节点之后,对链表进行拆环并返回新链表头节点即可;

看不懂解释的话,直接看算法图解比较容易理解点

复杂度分析:

时间复杂度:O(n),最坏情况下,我们需要遍历该链表两次。

空间复杂度:O(1)。我们只需要常数的空间存储若干变量。

算法图解

  红色部分代表当前遍历的节点,注意这里Kth的位置是从0开始的,Kth=3对应的位置4;(注:本人不会做成流程动画,希望会的朋友可以私信我指点一二,说个软件名字也可以,谢谢


三、代码实现

每个代码块都写了注释,方便理解,代码还可以改进;

方法一:快慢指针

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        // 预处理阶段
        if(head == null || head.next == null || k == 0) return head;
        ListNode temp = new ListNode(0, head);
        // 创建快慢指针
        ListNode fast = head, slow = temp, fast_prev = head; 
        int listlength = 0; // 链表长度
        // 找到快指针的位置, 新链表的尾节点
        for(int i = 0; i < k; i++){
            // 链表遍历结束时,k值还没有结束
            if(fast == null){
                fast = head.next;
                int templ = (k-1)%listlength;
                // System.out.println("templ = " + templ);
                for(int j = 0; j < templ; j++){
                    fast = fast.next;
                }
                // 找到快指针结束循环
                break;
            }
            fast = fast.next;
            listlength++;
        }
        if(fast == null) return head;
        // System.out.println("fast.val = " + fast.val);
        // 同时移动快慢指针
        while(fast != null){
            if(fast.next == null) fast_prev = fast;
            fast = fast.next;
            slow = slow.next;
        }
        // System.out.println("slow.val = " + slow.val);
        fast_prev.next = head;
        head = slow.next;
        slow.next = null;
        return head;
    }
}

提交结果:

方法二:闭合为环

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        // 预处理阶段
        if(k == 0 || head == null || head.next == null){
            return head;
        }
        
        int list_length = 1, Kth = 0;
        ListNode last = head, first;
        // 找到链表尾节点,并计算链表长度
        while(last.next != null){
            list_length++;
            last = last.next;
        }
        // (n-1)-(k%n)
        Kth = list_length - (k % list_length);
        if(Kth == list_length) return head;
        // 构建环
        last.next = head;
        // 根据公式计算出新链表的头节点位置并拆解环
        while(Kth-- > 0) last = last.next;
        first = last.next;
        last.next = null;
        return first;
    }
}

提交结果:


总结

感谢观看,如果有帮助到你,请给题解点个赞和收藏,让更多的人看到。🌹 🌹 🌹

也欢迎你,关注我。👍 👍 👍

原创不易,还希望各位大佬支持一下,你们的点赞、收藏和留言对我真的很重要!!!💕 💕 💕 最后,本文仍有许多不足之处,欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正!


相关文章
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
5天前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
7 1
|
29天前
链表指针的传参,传值和传地址
本文讨论了链表操作中指针传参的问题,特别是指针的传值与传地址的区别,并提供了修正代码,以确保链表插入操作能正确地修改指针指向的地址。
12 1
链表指针的传参,传值和传地址
|
2月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
|
25天前
|
存储
一篇文章了解区分指针数组,数组指针,函数指针,链表。
一篇文章了解区分指针数组,数组指针,函数指针,链表。
17 0
|
25天前
|
C语言
无头链表二级指针方式实现(C语言描述)
本文介绍了如何在C语言中使用二级指针实现无头链表,并提供了创建节点、插入、删除、查找、销毁链表等操作的函数实现,以及一个示例程序来演示这些操作。
19 0
|
3月前
|
存储 算法 数据处理
指针与链表
指针与链表
59 0
|
3月前
|
Python
【Leetcode刷题Python】1467. 两个盒子中球的颜色数相同的概率
本文介绍了LeetCode第50题"Pow(x, n)"的解法,题目要求实现计算x的n次幂的函数,文章提供了递归分治法的详细解析和Python实现代码。
36 0
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
52 6
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
106 2