关于单链表查环及其相关问题的数学证明（最完全最清晰）

2020-07-14 本文已影响0人培根炒蛋

未经许可严禁转载，侵权必究

描述

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步。如果存在环，则指针 slow 、fast会相遇。

如果环不存在，fast遇到NULL退出。

使用这种方法，有一个定律：

fast和slow一定会环内相遇。

我们这篇文章的主要目的就在于给出这个定律的证明。

2. 最广泛的错误证法：

如果两个指针的速度不一样，比如 $p$ ， $q$ ， $(0<p<q)$ 二者满足什么样的关系，可以使得两者肯定交与一个节点？

设 $p$ 为指针slow每步移动距离， $q$ 为指针fast的每步移动距离。
设当slow指针到环的入口时，fast指针已经在环里走过了 $k$

$Sp(i) = p*i$

如果两个要相交于一个节点，则
$Sq(i) = k + q*i$

$Sp(i) = Sq(i)$

$(p*i) \bmod n = ( k+ q*i ) \bmod n$

$[ (q - p) * i + k ] \bmod n =0$

$(q-p)i + k = N*n [N 为自然数]$

$i = (N*n -k) /(p-q)$
$i$ 取自然数，则当 $p$ ， $q$ 满足上面等式即存在一个自然数 $N$ ，可以满足 $N*n - k$ 是 $p - q$ 的倍数时，保证两者相交。

这个在互联网上最为广泛简洁的证明看似很有道理没什么问题，但是却有其致命的错误：

求模操作满足分配率吗?

我不会证求模操作是否满足分配率，但是运行如下代码(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))

输出结果：

unsatisfied : 393883
total : 970299

实际上求模操作是不满足像除法一样的分配率的

当然上面的错误也归功于百度百科给出的错误公式。
$(a+b) \mod p = ( a \mod p + b \mod p )$
实际上求模的分配率是这样的
$(a + b) \bmod n = [(a \bmod n) + (b \bmod n)] \bmod n$

同样给出一段代码:

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))

输出结果：