给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

示例 1：

**输入：**head = [3,2,0,-4], pos = 1
**输出：**true
**解释：**链表中有一个环，其尾部连接到第二个节点。

1

示例 2：

**输入：**head = [1,2], pos = 0
**输出：**true
**解释：**链表中有一个环，其尾部连接到第一个节点。

2

示例 3：

**输入：**head = [1], pos = -1
**输出：**false
**解释：**链表中没有环。

3

这个题大家都知道用一快一慢两个指针就能解决问题，但是这种想法比较反人类，为啥两个指针一快一慢就能在环中相遇，为啥快指针每次要走两步，走三步行不行，走3步会不会更快？

首先如果没有环，那快指针直接就走完了；
如果有环，关于快慢指针相遇我看到两个比较有意思的说法（就不公式推导了，有兴趣的可以看看这个关于Floyd's cycle-finding algorithm）：

  • 数学归纳法

如果快慢指针相差一步，那么慢指针走一步，快指针走两步，相遇；
如果快慢指针相差两步，那么慢指针走一步，快指针走两步，变成相差一步的情况；
如果快慢指针相差三步，那么慢指针走一步，快指针走两步，变成相差两步的情况；

  • 相对运动

慢指针相对快指针静止，快指针走一步，如果在环中最后就会相遇。

这两种说法见于逼乎，都是挺有趣而且比较形象的回答。

然后是关于快指针为何走两步，走三步行不行？四步行不行？
行，当然行！
为什么？
emmm，你开心就好。
让我们来假设环的长度为x,环之前的长度为y，快慢指针在环中相遇的位置距环的入口长度为i，快慢指针的比率为k。
慢指针走了y+i步,快指针走了y+i+mx步（m为快指针在环内循环的次数），以为快指针还是慢指针步数的k倍，所以快指针还相当于走了k(y+i)步，即我们可以得出k(y+i)=y+i+mx.

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null||head.next==null){
            return false;
        }
        ListNode slow = head;
        ListNode fast = head;
        
        do{
            if(fast==null||fast.next==null){
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }while(slow!=fast);
        return true;
    }
}
Last modification：November 5th, 2019 at 01:51 am
© 允许规范转载
大家一起分享知识，分享快乐