被滴滴小姐姐摁在地上摩擦

前段时间正在找工作，有幸接到滴滴的面试邀请，结果因为一个链表问题被摁在地上摩擦。

开始聊从项目、go 到 mysql 等方面聊得很愉快，最后小姐姐出了一道链表问题。

问题描述

滴滴小姐姐: 给链表判断是否有环？（心中暗喜，闭着眼都能写出来）

思路：快慢指针, 刷刷写完

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func hasCycle(head *ListNode) bool {
    if head == nil{
        return false
    }

    slow, fast := head, head.Next
    for slow != fast{
        if fast == nil || fast.Next == nil{
            return false
        }
        fast = fast.Next.Next
        slow = slow.Next
    }
    return true
}

滴滴小姐姐: 如果有链表有环，请用数学证明快慢指针一定能相遇。

现在想想真的很丢脸（无地自容），花了两个小时终于搞明白了。

分析

如上图

假设链表又环，fast在 node7 的时候，slow 进入 入环点 node3。

数学推导：

1. 假设 fast 到 slow 距离为 N, fast 比 slow 快一步。
2. 所以每走一步，两点距离：N+1-2 = N-1。
3. 一直到 N = 0 的时候，两个指针相遇。

总结： fast 多走 1 步、2 步、n 步都没有关系，因为两个指针的距离在缩短，相遇是必然的。

继续延伸: 链表入环点

滴滴小姐姐(已下线): 如果一个链表有环，请返回入环点。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
    if head == nil{
        return nil
    }
    fast, slow := head, head

    for {
        if fast == nil || fast.Next == nil{
            return nil
        }
        fast = fast.Next.Next
        slow = slow.Next

        if fast == slow {
            break
        }
    }

    fast = head
    for fast != slow{
        fast = fast.Next
        slow = slow.Next
    }
    return fast
}

滴滴小姐姐(已下线): 请用数学证明：第一次相遇的点到入环点的距离等于从头指针到入环点的距离。

证明过程：

1. 链表头结点到入环点的距离为 a，
2. 入环点到两个指针第一次相遇的点的距离为 b
3. 两个指针第一次相遇的点再到入环点的距离为 c
4. fast = a + b + c + b
5. slow = a + b
6. 由于 fast 是 slow 的两倍速度，
7. 2(a+b) = a + b + c + b
   -> 2a + 2b = a + c + 2b
   -> 2a = a + c
   -> a = c
8. 所以，第一次相遇的点到入环点的距离等于从头指针到入环点的距离。
9. fast 指针只能比 slow 指针多走一步。fast 多走几步没法成立。

复盘

在 leet code 刷题，大部分都是在刷熟练度（板砖别砸我），而常常忽略了本质。想起老师叮嘱的话：要知其然，还要知其所以然。