【2024考研】题解6 | #链表中环的入口结点#

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        if(!pHead || !pHead->next)return nullptr;
        //快慢指针
        ListNode *fast = pHead;
        ListNode *slow = pHead;
        bool hasCycle = false;

        //先判断是否有环
        while(fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast) {
                hasCycle = true;
                break;
            }
        }
        //没有就直接返回空值
        if(!hasCycle) return nullptr;

        //确定环长度
        int length = 1;
        fast = fast->next;
        while(fast != slow){
            fast = fast->next;
            length++;
        }
        //确定环入口节点位置
        slow = pHead;
        fast = pHead;
        for(int i = 0; i < length; i++){
            fast = fast->next;
        }
        while(slow != fast){
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }
};
/*
时间复杂度分析：

1.判断链表是否有环的过程中，快指针每次走两步，慢指针每次走一步，最多遍历n个结点，时间复杂度为O(n)。
2.确定环的长度的过程中，快指针每次走一步，最多遍历n个结点，时间复杂度为O(n)。
3.找到环的入口结点的过程中，快慢指针每次走一步，最多遍历n个结点，时间复杂度为O(n)。 
总的时间复杂度为O(n)。

空间复杂度分析： 只使用了常数个额外的变量，空间复杂度为O(1)。
*/