链表中环的入口结点

2020-05-01  本文已影响0人  su945

题目描述

给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。

问题分析

/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:

    ListNode* MeetNode(ListNode* pHead)
    {
        if (pHead == nullptr)
        {
            return nullptr;
        }
        //ListNode* Node = NULL;
        ListNode* slowNode = pHead->next;
        if (slowNode  == nullptr)
        {
            return slowNode ;
        }
        ListNode* fastNode = slowNode->next;
        
        while (fastNode != nullptr && slowNode != nullptr)
        {
            if (fastNode == slowNode)
            {
                return slowNode;
            }
            //更新
            slowNode = slowNode->next;
            fastNode = fastNode->next;
            if (fastNode->next != nullptr)
            {
                fastNode = fastNode->next;
            }
        }
    }

    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        //step1 判断是否有环
        ListNode* meetNode = MeetNode(pHead);
        if (meetNode == nullptr)
        {
            return nullptr;
        }
        //step2 判断环的长度
        ListNode* tmp = meetNode;
        int count = 1;
        while (tmp->next != meetNode)
        {
            tmp = tmp->next;
            count++;
        }

        //step3 找寻环的入口处
        ListNode* Node1 = pHead;
        ListNode* Node2 = pHead;
        for (int i = 0; i < count; ++i)
        {
            Node2 = Node2->next;
        }
        while (Node1 != Node2)
        {
            Node1 = Node1->next;
            Node2 = Node2->next;
        }
        return Node1;
    }
};

参考

https://github.com/WordZzzz/Note/commit/ad0df0a24ffcf94a5330b7a3574d76612381a8c0
https://www.nowcoder.com/questionTerminal/253d2c59ec3e4bc68da16833f79a38e4?f=discussion

上一篇 下一篇

猜你喜欢

热点阅读