美文网首页
【LeetCode-142 | 找到环形链表的入口节点】

【LeetCode-142 | 找到环形链表的入口节点】

作者: CurryCoder | 来源:发表于2021-12-28 22:34 被阅读0次
    1.jpg 2.jpg
    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    struct ListNode{
        int val;
        ListNode* next;
        ListNode(int x): val(x), next(nullptr) {}
    };
    
    
    class Solution {
    public:
        ListNode* detectCycle(ListNode* head) {
            ListNode* fast = head;
            ListNode* slow = head;
            // 1.判断链表是否有环
            while(fast && fast->next) {
                fast = fast->next->next;
                slow = slow->next;
                // 2.快慢指针相遇,则说明链表有环
                if(fast == slow) {
                    ListNode* index1 = head;
                    ListNode* index2 = fast;
                    // 3.利用"快慢指针在环内相遇点处到环入口节点的距离 == 头节点到环入口节点的距离"原理,找到环的入口节点
                    while(index1 != index2) {
                        index1 = index1->next;
                        index2 = index2->next;
                    }
                    return index1;
                }
            }
            return nullptr;
        }
    };
    

    相关文章

      网友评论

          本文标题:【LeetCode-142 | 找到环形链表的入口节点】

          本文链接:https://www.haomeiwen.com/subject/ecfmqrtx.html