当前位置: 首页> 游戏> 游戏 > 【快慢指针】突破环形链表

【快慢指针】突破环形链表

时间:2025/7/9 7:34:03来源:https://blog.csdn.net/2301_79263365/article/details/142325023 浏览次数:0次

 

 🚀个人主页:一颗小谷粒 

 🚀所属专栏:力扣刷题

很荣幸您能阅读我的文章,诚请评论指点,欢迎欢迎 ~

目录

一、链表的中间结点

1.1 题目要求

1.2 图解分析

1.3 Java代码实现 

1.4 复杂度分析

二、环形链表 I

2.1 题目要求

2.2 算法分析

2.3 Java代码实现

2.4 复杂度分析

三. 环形链表 II

3.1 题目要求

3.2 图解分析

3.3 Java代码实现

3.4 复杂度分析 

四、总结 


一、链表的中间结点

 

首先,让我们通过一道找链表的中间结点的题目来认识一下什么是快慢指针,以及它在题中是如何运用的!

1.1 题目要求

leetcode876.链表的中间结点 这道题就可以使用快慢指针来解答,题目如下:

876. 链表的中间结点 - 力扣(LeetCode)

1.2 图解分析

我们用两个指针指向链表的头结点,一个叫快指针(fast),一个叫慢指针(slow),每次循环慢指针走一步,快指针走两步。

若链表长度为3 ,一次循环后结束,如图:

若链表长度为5 ,两次循环后结束,如图:

链表长度为奇数的时候,若快指针在最后一个节点,那么慢指针一定在中间节点 

那么链表长度为偶数呢?

以链表长度为2举例,一次循环后结束,如图:

 若链表长度为4 ,两次循环后结束,如图:

 对于偶数节点,如果快指针指向空,那么慢指针一定在中间节点上

 综合两种情况,当快指针指向空,或者它的下一个节点指向空,这个时候就退出循环

1.3 Java代码实现 

    public ListNode middleNode(ListNode head) {ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}return slow;}

1.4 复杂度分析

  • 当快指针走到链表末尾的时候循环就结束了,所以时间复杂度是O(n)的。
  • 空间复杂度由于我们只用到若个额外变量,所以它是O(1)的。

OK!通过这道题相信大家对快慢指针已经有了一个基本的认识了~~

二、环形链表 I

2.1 题目要求

leetcode.141 题目如下:

141. 环形链表 - 力扣(LeetCode)

2.2 算法分析

慢指针每次循环走一步,如果图中有环的话,那么慢指针一定会进入到环中,由于快指针相对于慢指针每次循环多走了一步,所以快指针肯定会与慢指针相遇。

所以我们只需要在第一题代码每次循环时判断快慢指针是否会相遇即可! 如果链表成环,快慢指针一定会相遇!

2.3 Java代码实现

    public boolean hasCycle(ListNode head) {ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if(slow==fast){return true;}}return false;}

2.4 复杂度分析

  • 由于慢指针进入环后,我们的循环次数是小于环的长度的,所以时间复杂度是O(n)的。
  • 空间复杂度O(1)的,因为我们只用到若个额外变量。

三. 环形链表 II

3.1 题目要求

leetcode.142 题目如下:

142. 环形链表 II - 力扣(LeetCode)

这个题与141相比,不仅要判断是否有环,还要找到环的入口!

3.2 图解分析

如图所示:

  • 环长 = b + c
  • 慢指针移动距离 = a + b
  • 快指针移动距离 = a + k(b+c) + b

由于快指针移动距离是慢指针的两倍 ,所以推导得:

 

那么 a - c = (k - 1)(b +c) 意味着什么呢? 

slow 从相遇点出发,head从头节点出发,走c步后,slow在入口,head 到入口的距离也恰好是环长的倍数,继续走,两者必然会在入口相遇 ! 

这里有个结论:当快慢指针相遇时,慢指针还没有走完一整圈  

大家可以在本子上画图来一步步模拟这个过程,相信你会理解的!

3.3 Java代码实现

    public ListNode detectCycle(ListNode head) {ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if(slow==fast){while(slow!=head){slow = slow.next;head = head.next;       }return slow;}}return null;}

3.4 复杂度分析 

  • 时间:O(n)
  • 空间:O(1)

四、总结 

这三个题都有相似之处,都运用了快慢指针的方法来解决,第一遍做可能无法体会,反复琢磨,相信你会理解它的原理,顿悟其中的奥妙!



 本次的分享就到此为止了,希望我的分享能给您带来帮助,创作不易也欢迎大家三连支持,你们的点赞就是博主更新最大的动力!如有不同意见,欢迎评论区积极讨论交流,让我们一起学习进步!有相关问题也可以私信博主,评论区和私信都会认真查看的,我们下次再见

 博主wx:g2279605572 

关键字:【快慢指针】突破环形链表

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: