环形链表问题

给定一个链表，判断链表中是否有环。存在环返回 true ，否则返回 false

分析：

该题可以理解为检测链表的某节点能否二次到达（重复访问）的问题。
需要一个容器记录已经访问过的节点 每次访问到新的节点，都与容器中的记录进行匹配，若相同则存在
环 若匹配之后没有相同节点，则存入容器，继续访问新的节点 直到访问节点的next指针返回null，或者
当前节点与容器的某个记录相同，操作结束。
实现简单，时间复杂度为：
遍历整个链表：O(n)
每次遍历节点，再遍历数组进行匹配：O(n)
换个思路：
该题可以理解为“追击相遇”问题，如果存在环，跑得快的一定能追上跑得慢的。
比如：一快一慢两个运动员，如果在直道赛跑，不存在追击相遇问题；如果是在环道赛跑，快的绕了一
圈肯定可以追上慢的。

解法：

1. 定义快慢两个指针：
   slow=head; fast=head.next;
2. 遍历链表：
   快指针步长为2：fast=fast.next.next; 慢指针步长为1：slow=slow.next;
3. 当且仅当快慢指针重合(slow==fast)，有环，返回true
4. 快指针为null，或其next指向null，没有环，返回false，操作结束

代码

package com.david.line.linkedlist; 

/**
* 环状链表 
*/ 
public class RingList { 
    public static boolean isRing(Node head){ 
        if(head==null) return false; 
        //定义快慢指针 
        Node slow=head; //慢指针 
        Node fast=head.next; //快指针
        while(fast!=null&&fast.next!=null){ 
            //有环 
            if(slow==fast){ 
                return true; 
            }
            fast=fast.next.next;// 快指针步长为2 
            slow=slow.next;//慢指针步长为1 
        }
        return false; 
    }
    
    public static void main(String[] args) { 
        Node n1=new Node(1,"张飞"); 
        Node n2=new Node(2,"关羽"); 
        Node n3=new Node(3,"赵云"); 
        Node n4=new Node(4,"黄忠"); 
        Node n5=new Node(5,"马超"); 

        n1.next=n2; 
        n2.next=n3; 
        n3.next=n4; 
        n4.next=n5; 
        n5.next=n1; 
        
        System.out.println(isRing(n1)); 
    } 
}

此种算法的时间复杂度为：O(n)