使用java判断环形链表的起点，Leetcode 142题

判断环形链表的起点（java语言）Leetcode 142题

Leetcode 142题 判断环形链表的起点

在这里我们是使用快慢指针 (双指针) 的方式来解决此问题。

​ 我们设置一个慢指针指向头结点，快指针指向头结点，快指针每次走两步，慢指针每次走一步。如果不存在环，快指针最终会指向null；如果存在环，两者最终必定在环中的某一点相遇。这是一个数学中的追击问题，两个运动员在环形跑道上匀速跑步，一个快，一个慢，慢的一方一定会被快的一方在一定时间内追上。(题外话，该论证是一个小学问题，但是我还是思考了很久，只能说智商多少沾点)，所以我们得到如何判断链表中是否存在环的条件，即快慢指针最终相遇。

​ 有了判断是否存在环的条件，接下来我们在来探讨一个问题，那就是如何找到链表中环的起点。我们假设：

将带环链表拆分成一个单链和一个环，结构如下图：

​ 单链的长度为a，环的长度为c，两者在环中的c点相遇，注意，这个c点是距离环的起点的单圈距离。

​ 设慢指针走的路程为s，快指针走的路程是f，这里是路程，不是距离或者是位移。快指针在环上走了m圈，慢指针在环上走了n圈，所以我们能够得出：

s = a + n * b + c

f = a + m * b + c

​ 同时，因为快指针每次走两步，慢指针每次走一步，两者最终相遇，那么我们可以得出： f = 2 s；

所以我们能够得出 ：a + m * b + c = 2 * ( a + n * b + c)

​ 化简得 ：a + c = (m - 2n) * b

​ 即 ：a + c 是 b 的整数倍，即我们从c点出发，走a步会到达环头，可能走了很多圈。

所以我们在两个快慢指针第一次相遇的时候，将慢指针再次指向头结点，快指针指向相遇的结点，两者以同样的速度（一步）前进，直至相遇，则环的起点找到。

以下是代码：java版本

  public ListNode detectCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    //证明有环的方法（当然我们也可以不使用快慢指针判断是否存在环）

    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) {
            break;
        }
    }

    //head为空或者head只有一个结点的情况

    if (fast == null || fast.next == null) {
        // fast 遇到空指针说明没有环
        return null;
    }
    // 慢指针重新指向头结点
    slow = head;
    // 快慢指针以相同的速率前进，直到相遇
    while (slow != fast) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

本人刷题心得，如有错误和冒犯，欢迎指正。