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

为了表示给定链表中的环,我们使用整数 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
大家一起分享知识,分享快乐