使用快慢指针求解「环形链表」so easy！

喜欢ヅ旅行 2021-12-21 14:59 172阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，一起学算法

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

今天分享的题目来源于 LeetCode 上第 141 号问题：环形链表。题目难度为 Easy，目前通过率为 40.4% 。

使用快慢指针的方式去求解 **so easy** ！

### 题目描述 ###

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 `pos` 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 `pos` 是 `-1`，则在该链表中没有环。

**示例 1：**

输入：head = [3,2,0,-4], pos = 1输出：true解释：链表中有一个环，其尾部连接到第二个节点。true
    解释：链表中有一个环，其尾部连接到第二个节点。

**示例 2：**

输入：head = [1,2], pos = 0输出：true解释：链表中有一个环，其尾部连接到第一个节点。true
    解释：链表中有一个环，其尾部连接到第一个节点。

**示例 3：**

输入：head = [1], pos = -1输出：false解释：链表中没有环。false
    解释：链表中没有环。

**进阶：**

你能用 O(1)（即，常量）内存解决此问题吗？

### 题目解析 ###

这道题是快慢指针的**经典应用**。

设置两个指针，一个每次走一步的**慢指针**和一个每次走两步的**快指针**。

### 动画描述 ###

![640?wx\_fmt=gif][640_wx_fmt_gif]

### 代码实现 ###

//author:程序员小吴public class Solution {    public boolean hasCycle(ListNode head) {        ListNode slow = head, fast = head;        while (fast != null && fast.next != null) {            slow = slow.next;            fast = fast.next.next;            if (slow == fast) return true;        }        return false;    }}
    public class Solution {
        
        public boolean hasCycle(ListNode head) {
        
            ListNode slow = head, fast = head;
            while (fast != null && fast.next != null) {
        
                slow = slow.next;
                fast = fast.next.next;
                if (slow == fast) return true;
            }
            return false;
        }
    }

## END ##

## ![640?wx\_fmt=png][640_wx_fmt_png] ##

**原 创 热 文 推 荐**

☞[毕业十年后，我忍不住出了一份程序员的高考试卷][Link 1]

[☞][Link 2][一道腾讯面试题：厉害了我的杯][Link 3]

[☞][Link 4][十大经典排序算法动画与解析，看我就够了][Link 5]

[☞][Link 4][这或许是东半球分析十大排序算法最好的一篇文章][Link 6]

[☞][Link 4][面试官，我会写二分查找法！对，没有 bug 的那种！][bug]

![640?wx\_fmt=png][640_wx_fmt_png 1] 你点的每个“在看”，我都认真当成了喜欢

[640_wx_fmt_jpeg]: /images/20211220/bdb9dfcd644c4e4e92060df19b48cdae.png
[640_wx_fmt_gif]: /images/20211220/d2cf405e1bc6415db0c427f8e635fa83.png
[640_wx_fmt_png]: /images/20211220/944d78b0d57c4f54924b1abe5f468c0c.png
[Link 1]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/91488249
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzA5MzY4NTQwMA==&mid=2651011536&idx=3&sn=fd5ff61a84fe2180a7c21d15acf71659&chksm=8bad8a27bcda03319570ae23d05392d287390a51ca94014422dd199450b25f43467aaaedb59e&scene=21#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484557&idx=1&sn=739d80488fe1169a9c9ca26ecfcdfba6&chksm=fa0e6b0ccd79e21a1c2b0d99db69f6206cddddfe2367742e9de1d7d17ec35a5ce29fa4e30d63&scene=21#wechat_redirect
[Link 4]: http://mp.weixin.qq.com/s?__biz=MzA5MjcxNjc2Ng==&mid=2650560116&idx=1&sn=f9e86fa3e7b15624177b29ef1a785be4&chksm=88601dc5bf1794d30fd595d413491da189584b44fd2b2e5e40c665e58760e162616585811647&scene=21#wechat_redirect
[Link 5]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/87910210
[Link 6]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/92825279
[bug]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485240&idx=1&sn=fbccc747b2e8558c6478171709005ff9&chksm=fa0e68b9cd79e1af5ab68d42adea0b24c7d4867069091df9e95b6f20ab57b69c4e38994a36be&scene=21#wechat_redirect
[640_wx_fmt_png 1]: /images/20211220/8b83976c560d4977b9839e394c84e297.png