【算法分析与设计】环形链表

题目

给你一个链表的头节点?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
解释：链表中没有环。

思想（快慢指针）

快慢指针方法也被称为 Hare & Tortoise 算法，该算法会使用两个在数组（或序列/链表）中以不同速度移动的指针。该方法在处理循环链表或数组时非常有用。

该算法的应用场景：

• 处理链表或数组中的循环的问题
• 找链表中点或需要知道特定元素的位置

何时应该优先选择这种方法，而不是上面提到的二指针方法？

• 有些情况不适合使用二指针方法，比如在不能反向移动的单链接链表中。使用快速和慢速模式的一个案例是当你想要确定一个链表是否为回文（palindrome）时。

算法分析与设计?

1. 初始化： 两个指针fast和slow都指向链表的头部。
2. 循环条件： 使用一个无限循环，每次迭代中，fast指针向前移动两步，而slow指针向前移动一步。
3. 终止条件： 如果链表中存在循环，fast指针最终会追赶上slow指针，导致它们相遇。如果链表不存在循环，fast指针会提前到达链表尾部。
4. 返回结果： 如果相遇，说明链表中存在循环，返回true；否则，返回false。

代码实现

/**
 * 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 fast=head;
        ListNode slow=head;
        if(head==null||head.next==null){
            return false;
        }
        while(true){

            if(fast==null||fast.next==null){
                return false;
            }
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
               return true;
            }
           
        }
   
    }
}

运行结果

• 如果链表中不存在循环，时间复杂度为O(n)，其中n是链表的长度。
• 空间复杂度是O(1)