博客

对于

链表找环路

的问题，有一个通用的解法——

快慢指针（Floyd 判圈法）

。给定两个指针，分别为 slow 和 fast，起始位置均在链表的开头。每次 fast 前进两步，slow 前进一步。如果 fast可以走到尽头，那么说明没有环路；

如果 fast 可以无限走下去，那么说明一定有环路，且一定存在一个时刻 slow 和 fast 相遇。

当 slow 和 fast 第一次相遇时，我们将 fast 重新移动到链表开头，并让 slow 和 fast 每次都前进一步。当 slow 和 fast 第二次相遇时，相遇的节点即为环路的开始点。

下图可简要说明：f代表快指针，s代表慢指针。假设图中×点为f与s第一次相遇点，实心点代表环入口，此时s再走a步即可到达环入口。如何测量a步？另fast指针移到head处，每次走一步，与slow同步，再次相遇点及环入口。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head,slow=head;
        while(true){
        	//没有环路的直接返回null
            if(fast==null || fast.next==null){
                return null;
            }
            fast=fast.next.next;
            slow=slow.next;
            //fast与slow相遇，代表有环
            if(fast==slow) break;
        }
        fast=head;
        //fast与slow再次相遇点即环入口。
        while(fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }
        return fast;
    }
}