链表中环的入口结点

题目描述

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

问题分析

• step1 判断是否有环
  采用快慢指针的模式，如果快指针和慢指针同时指向同一个地址，说明有环。此时的相遇点在环上。
• step2 判断环的长度
  从相遇点出发，经过多少步再次指向相遇点，此时记录的步数即为环的长度
• step3 找寻环的入口处
  从指针1和指针2表头出发，指针1先走环的长度，然后同时按相同的步数出发，当指针1和指针2相遇的位置即为环的入口处。

  解题思路1

/*
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