141. Linked List Cycle.md

141. Linked List Cycle

Problem

Given a linked list, determine if it has a cycle in it.

Follow up: Can you solve it without using extra space?

tag:

Solution

快慢指针，slow一次移动一步，fast一次移动两步， 如果两个指针相遇，则存在环。

证明： 如图， 设交点为M，环的起点为E，|HE| = L1， |EM|=L2, 环的长度为 C，

1. 第一个（速度慢的）指针在环里转满一圈之前，两个指针必然相遇 设 slow第一次进入环时，fast在slow前方 a处， 经过x次移动后两指针相遇, 则x = (2x+a)%C => x=C-a

2. 相遇位置 2*(L1+L2) = L1+L2+nC => L1+L2=nC 即， 两指针相遇时，令fast指针重新从H点开始，一次移动一步，则fast, slow必定在环起点相遇

java

    public ListNode detectCycle(ListNode head) {
        if(head==null||head.next==null) return null;
        ListNode f = head, s = head;
        while(f!=null && f.next!=null) {
            f = f.next.next;
            s = s.next;
            if(f==s) break;
        }
        if(f!=s) return null;
        f = head;
        while(f!=s) {
            f = f.next;
            s = s.next;
        }
        return f;
    }

go