2.6给定一个有环链表,实现一个算法返回环路的开头结点。

书上写的好复杂。

1、检测链路是否存在环路。通过FastRunner/SlowRunner法,FastRunner一次移动两步,SlowRunner一次移动一步。

2、当二者碰到之后,F继续走,S从头走。当他们再次碰头时,那就是环的入口。

建议:空想好难,建议随便列几个数字看看规律。

LinkedListNode FindBeginning(LinkedListNode head)
{
    LinkedListNode slow = head;
    LinkedListNode fast = head;
    
    //找出碰撞处,会处于链表中LOOP_SIZE - k步的位置
    while (fast != null && fast.next != null)
    {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast)
        {
            break;
        }
    }
    
    //错误检查,没有碰撞处,也即没有环路
    if (fast == null || fast.next == null)
    {
        return null;
    }
    
    //slow重新开始走,fast减速接着走
    slow = head;
    while (slow != fast)
    {
        slow = slow.next;
        fast = fast.next;
    }
    
    return fast;
}
原文地址:https://www.cnblogs.com/yangtoujunshi/p/7764554.html