题目描述

blablabla

样例

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *entryNodeOfLoop(ListNode *head) {
        //快指针p1，慢指针p2，速度2:1.一直走，知道p1==p2或者p1==NULL
        ListNode* p1, * p2;
        p1 = p2 = head;
        if(!head ) return 0;//链表为空直接返回空
        int t = 0;
        while(p1 &&p2)
        {
            p1 = p1->next;//一步一步来，防止p1步子迈得太大(p1 = nullptr->next)
            p2 = p2->next;
            t++;
            if(p1) p1 = p1->next;
            if(p1 && p1 == p2) break; 
        }
        if(p1 == NULL) return 0;//如果p1 == NULL 无环
        p2 = head;//否则有环，令p2从头开始（p1仍在第一次相遇点）
        for(int i = 0; i < t;i++)
        {
            p1 = p1->next, p2 = p2->next;//二者步长都是1
            if(p1 == p2) return p1;//必定相遇于环入口
        }
    }
};
blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla