使用快慢指针判断单链表是否有环_快慢指针判断链表是否有环

如何判断单链表内是否有环

        使用快慢指针判断。

        实现思路：分别用fast和slow指针从链表头出发，fast每次前进2步，slow每次前进1步。如果链表内有环，则两个指针一定相遇；如果快指针走到链表尾部，则链表内没有环。

        代码实现：

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }//当传入的是空指针，直接返回false
        // 不加一些用例会报空指针异常
 
 
        ListNode fast = head;
        ListNode slow = head;//快慢指针
        while (head.next != null) {
            fast = fast.next;
            if (fast == null) {
                return false;
            }
            fast = fast.next;
            if (fast == null) {
                return false;
            }
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }//如果想找到环入口，在快慢指针相遇时，起点创建一个指针，和慢指针同步往下走，第一次相遇一定在入口处
        return false;
 
    }
}

        实现原理：fast指针每次比slow指针多走一步，所以最终一定能追上慢指针。

        时间复杂度：O(n)。

        空间复杂度：O(1)。

如何找到环的入口

        在快慢指针相遇时，创建一个新的指针，从表头出发。slow指针和新指针同步前进，当两指针相遇时，相遇的地方就是环的入口。

        证明：

        快慢指针相遇时：慢指针前进了m+x步，快指针前进了m+nr+x步。（n为环的圈数，n>=1）

        新指针和slow指针：当到达入口时，新指针前进了m步，慢指针前进了r-x+(n-1)r步。两者相等，证明相遇时的节点就是入口。