未經(jīng)許可嚴禁轉(zhuǎn)載，侵權(quán)必究

相關(guān)題目:

141. Linked List Cycle
142. Linked List Cycle II

這道題的具體描述和解題代碼就不多做解釋了，寫關(guān)于解法的多如牛毛，下功夫都能明白這道題應(yīng)該都能清楚是怎么做的。

順便說一下，這種找重復(fù)的問題首先要想到的是要用HashSet去解決，O(n)的方法如果你沒見過的話是很難想出來的。

但是最關(guān)鍵問題在于，解法雖然簡單，但是怎么證明你的解法是對的，除了leetcode的黑盒測試，給出一個數(shù)學(xué)上的一般化證明是十分必要。

我看了網(wǎng)上的很多資料，絕大多數(shù)給出的證明都是錯的，只是瞎貓碰死耗子碰對了，要么剩下的就極其繁瑣文字眾多并且一些地方非常模糊。

不想看描述和解法的可以直接跳過下面的部分。

描述

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

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

image

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.

image

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

image

141 解:

public class Solution {
    public boolean hasCycle(ListNode head) {
            ListNode slow = head, fast = head;
            while (slow != null) {
                if (fast.next == null || fast.next.next == null) {
                    break;
                }
                slow = slow.next;
                fast = fast.next.next;
                if (slow == fast) {
                    return true;
                }
            }
            return false;
    }
}

142 解:

public class Solution {
    private ListNode getIntersect(ListNode head) {
        ListNode tortoise = head;
        ListNode hare = head;

        // A fast pointer will either loop around a cycle and meet the slow
        // pointer or reach the `null` at the end of a non-cyclic list.
        while (hare != null && hare.next != null) {
            tortoise = tortoise.next;
            hare = hare.next.next;
            if (tortoise == hare) {
                return tortoise;
            }
        }

        return null;
}

    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }

        // If there is a cycle, the fast/slow pointers will intersect at some
        // node. Otherwise, there is no cycle, so we cannot find an entrance to
        // a cycle.
        ListNode intersect = getIntersect(head);
        if (intersect == null) {
            return null;
        }

        // To find the entrance to the cycle, we have two pointers traverse at
        // the same speed -- one from the front of the list, and the other from
        // the point of intersection.
        ListNode ptr1 = head;
        ListNode ptr2 = intersect;
        while (ptr1 != ptr2) {
            ptr1 = ptr1.next;
            ptr2 = ptr2.next;
        }

        return ptr1;
    }
}

1. 大致解題思路：

給兩個指針:

• slow : 每次走一步
• fast：每次走兩步

slow，fast指針從頭開始掃描鏈表。指針 slow 每次走1步，指針 fast 每次走2步。如果存在環(huán)，則指針 slow 、fast會相遇。

如果環(huán)不存在，fast遇到NULL退出。

使用這種方法，有一個定律：

fast和slow一定會環(huán)內(nèi)相遇。

我們這篇文章的主要目的就在于給出這個定律的證明。

2. 最廣泛的錯誤證法：

如果兩個指針的速度不一樣，比如，，二者滿足什么樣的關(guān)系，可以使得兩者肯定交與一個節(jié)點？

設(shè)為指針slow每步移動距離，為指針fast的每步移動距離。
設(shè)當slow指針到環(huán)的入口時，fast指針已經(jīng)在環(huán)里走過了

2. 如果兩個要相交于一個節(jié)點，則
   

取自然數(shù)，則當 ，滿足上面等式 即存在一個自然數(shù)，可以滿足 是 的倍數(shù)時，保證兩者相交。

這個在互聯(lián)網(wǎng)上最為廣泛簡潔的證明看似很有道理沒什么問題，但是卻有其致命的錯誤：

求模操作滿足分配率嗎?

我不會證求模操作是否滿足分配率，但是運行如下代碼(python)，可以證明上面證明步驟 4->5 是錯誤的:

ks = range(1,100,1)
ns = range(1,100,1)

total = len(ks) * len(ks) * len(ns)
i = 0
for n in ns:
    for k1 in ks:
        for k2 in ks:
            if (k1 + k2) % n != k1 % n + k2 % n:
                i += 1
                #print('k1 : {} k2 : {} n :{}'.format(k1,k2,n))
print('unsatisfied : {}'.format(i))
print('total : {}'.format(total))

輸出結(jié)果：

unsatisfied : 393883
total : 970299

實際上求模操作是不滿足像除法一樣的分配率的

當然上面的錯誤也歸功于百度百科給出的錯誤公式。

實際上求模的分配率是這樣的

同樣給出一段代碼:

ks = range(1,100,1)
ns = range(1,100,1)

i = 0

for n in ns:
    for k1 in ks:
        for k2 in ks:
            if (k1 + k2) % n != (k1 % n + k2 % n) % n:
                i+=1

print('unsatisfied : {}'.format(i))
print('total : {}'.format(total))

輸出結(jié)果：

unsatisfied : 0
total : 970299

3. 正確的證法：

設(shè)快慢指針slow，fast

設(shè)從開始走過的總步數(shù)為

設(shè)非環(huán)部分的長度為，環(huán)的長度為

1. 假設(shè)當slow進入環(huán)，從開始走過s步相遇有：
   

2. 即兩者余數(shù)相同時等式成立，設(shè)余數(shù)為，設(shè)slow 指針在環(huán)中走過了圈，fast指針在環(huán)中走過了圈，可得

5. 推出
   

上面這個式子明顯是成立的，因為 且
這里很明顯

又因

所以當為，為正整數(shù)時

5 式成立

當

6 式成立，并能使最小。

至于是多少，具體要取決于鏈表中非環(huán)和環(huán)的長度之比，因為 即使得時 6 式成立。

從而可以得出推論，

當 時

當 時

根據(jù)以上的證明，關(guān)于單鏈表查環(huán)相關(guān)的問題都可以迎刃而解。

4. 求環(huán)的長度

slow與fast相遇后，slow再次與fast相遇，計算slow走過的步數(shù)就是環(huán)的長度。

太過淺顯請讀者自證。

5. 求環(huán)的入口

這里我們可以利用上面快慢指針相遇的結(jié)論，假設(shè)同上：

根據(jù)上面的結(jié)論，假設(shè)當slow和fast相遇時，相遇點為，其中是環(huán)內(nèi)的點

1. 當兩個指針相遇時可以得到
   

3. 化簡可得
   
4. 等式兩邊同時 mod
   
5. 當且僅當下式滿足時等式成立
   
6. c為余數(shù)，可得
   
7. 可得
   
8. 最終得到結(jié)論
   

這樣我們可以得到一個結(jié)論，我們設(shè)定一個頭指針，從head 開始走，在slow和fast指針第一次相交的位置，slow指針開始走，當head指針走到環(huán)的入口，即slow指針在環(huán)里走了 步，head指針與slow指針相交，找到環(huán)的入口。

最后只附上一個英文資料，是leetcode美國版上的，他的證明雖然對，但是有點太魔幻，不是很容易理解：
https://leetcode.com/articles/linked-list-cycle-ii/

這個單鏈表查環(huán)問題的問題有個專有名稱：Floyd's Tortoise and Hare或者Floyd判圈法

因為我看到的中文資料幾乎全部有問題，當然也不排除我的做法本身也有問題，因為我的數(shù)學(xué)功底本身就很弱，如果是行家的話應(yīng)該能從我的過程看的出來，這就麻煩一些精通數(shù)學(xué)證明的朋友們來幫忙指正了。