『题目测试样例有问题？』极限的应用

思路『极限思维』

• 如图，假设『黄色部分的环足够大，导致，low指针从开始到相遇的红色点就走一次性到的，此时fast指针正好『第一回』重新追上！！也是在那』
• 导致公式成立：
• low=X+A
• fast=X+A+（B+A）
• 而我们发现，fast比low总是多走一倍，所以，我们发觉：fast=2*low
• 显然知道方程的答案是：B==X
• 所以，写出代码：
• low继续走，我们重新从起点发车一个low类型的指针，一定『第1回』就能在入口点相遇

面试时写的代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

//判断是否有环，有返回nullptr，否则返回相遇position
ListNode * isLoop( ListNode * head )
{
    if( nullptr==head || nullptr==(head->next) )
    {
        return nullptr;
    }

    ListNode * low=head;
    ListNode * fast=head;
    while( nullptr!=low && nullptr!=fast )
    {
        low=low->next;
        fast=fast->next;
        if( nullptr==fast )
        {
            return nullptr;
        }
        fast=fast->next;
        if( nullptr==fast )
        {
            return nullptr;
        }

        if( low==fast )
        {
            return low;
        }

    }

    return nullptr;
}

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if( nullptr==isLoop(head) )
        {
            return nullptr;
        }

        ListNode * pos=isLoop( head );
        ListNode * Help=head;

        while( 1 )
        {
            pos=pos->next;
            Help=Help->next;
            if( pos==Help )
            {
                return pos;
            }
        }

        //给编译器吃
        return nullptr;
    }
};

• 结果

  我放在牛客上去测试，发现：
  14/15 组用例通过
    运行时间 11ms
    占用内存 976KB
  用例输入
  {1,2},0
  预期输出
  1
  实际输出
  2
  
    但是，这个样例我觉得有问题，1和2入口，都是一样的吧。
  『解释如下：1连接到2,2连接到1』
    所以，我觉得我的应该是对的！！