从小白开始刷算法 双指针篇 leetcode.141

141. 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1

输出：true

解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0

输出：true

解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1

输出：false

解释：链表中没有环。

题目来源：力扣（LeetCode）

快慢双指针思路

能否写出：能写出。

时间：10多分钟

思路：

首先，判断给定的链表是否为空。如果为空，则肯定不存在环，直接返回 false。

1. 使用两个指针 slow 和 fast，初始时都指向链表的头节点 head。
2. 进入循环，每次循环中，慢指针 slow 移动一步，快指针 fast 移动两步。
3. 在每次移动之后，都判断快指针 fast 和慢指针 slow 是否相遇。如果相遇，则说明链表存在环，返回 true。
4. 如果快指针 fast 移动到链表的末尾（即 fast 或 fast.next 为 null），则说明链表不存在环，返回 false。
5. 重复步骤 3-5，直到链表遍历结束。

该算法的关键点是利用两个不同速度的指针进行遍历，如果链表存在环，那么快指针 fast 最终一定会追上慢指针 slow，从而产生相遇的情况。如果链表不存在环，那么快指针 fast 最终会到达链表的末尾，没有相遇的情况。

通过以上的思路和实现，可以判断给定的链表是否存在环，并返回相应的结果。

//

// 仅是我的思路代码，leetcode上大神更厉害
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null){
            return false;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast!=null&&fast.next!= null){
            fast = fast.next.next;
            slow = slow.next;
            if(slow == fast){
                return true;
            }
        }
        return false;
    }
}

时间复杂度：O(n) 链表长度n

空间复杂度：O(1)