LeetCode 判断链表中是否有环

桃扇骨 2023-10-11 11:32 49阅读 0赞

**判断链表中是否有环**

#### 题目描述： ####

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

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

![在这里插入图片描述][20190923093628331.png]  
示例 2：

输入：head = \[1,2\], pos = 0  
输出：true  
解释：链表中有一个环，其尾部连接到第一个节点。  
![在这里插入图片描述][20190923093701285.png]  
示例 3：

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

![在这里插入图片描述][20190923093722203.png]

**题目分析：**  
**我在这里用到的方法是：利用快慢指针来进行判断**  
**原理很简单：让快指针比慢指针快一倍的同时遍历链表：如果链表中存在环，那么快慢指针就会在循环一定次数后同时指向同一个节点，否则就会因为指向链表尾部null结束遍历。**  
**就像是两名运动员在操场上跑步一样，在理想情况下，快的会超过慢的运动员，和慢的运动员在某个时间点在环形的操场上在某个地点相遇。**

**java代码实现如下：**

/**
     * Definition for singly-linked list.
     * class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    public class Solution {
        public boolean hasCycle(ListNode head) {
            ListNode quick = head;
            ListNode slow = head;
            while(quick!=null && quick.next!=null){
                quick = quick.next.next;
                slow = slow.next;
                if(quick == slow){
                    return true;
                }
            }
            return false;
        }
    }

[20190923093628331.png]: https://img-blog.csdnimg.cn/20190923093628331.png
[20190923093701285.png]: https://img-blog.csdnimg.cn/20190923093701285.png
[20190923093722203.png]: https://img-blog.csdnimg.cn/20190923093722203.png