2021/04/22

前言

如下链表是一个带环链表，环的入口是 2，环的长度为 4。

链表节点定义如下：

// 单链表节点定义，参考 Leetcode
class ListNode<T> {
    public T val;
    public ListNode<T> next;

    public ListNode(){
        this(null,null);
    }

    public ListNode(T val){
        this(val,null);
    }

    public ListNode(T val, ListNode next){
        this.val = val;
        this.next = next;
    }
}
复制代码

判断链表是否有环

判断链表是否有环，比较好的方法是 快慢指针法。

定义两个指针 fast, slow ，初始都指向头节点。快指针 fast 一次向后移动一位，慢指针 slow 一次向后移动两位；如果快慢指针相遇（指向同一个节点且都不为空），说明链表存在环。

// 判断链表是否有环
public boolean isLoop(){
    if(this.head == null){
        return false;
    }
    ListNode<T> fast = head;
    ListNode<T> slow = head;
    while(fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if(fast == slow){
            return true;
        }
    }
    return false;
}
复制代码

确定环入口

如果链表存在环，如何确定环的入口（环交汇的节点）是哪个节点？

假设链表环的入口为 entrance ，快慢指针相遇的节点为 meet，由于快指针的速度是慢指针的 2 倍，所以当快慢指针相遇时，慢指针走过的距离为 s，则快指针走过的距离为 2s。

假设头节点到环入口的距离为 he，环入口到相遇节点的距离为 em，环的长度为 r。

我们可以得到：