链表中环的入口节点

题目：如果一个链表中包含环，如何找出环的入口节点？

解决这个问题的第一步是如何确定一个链表中包含环。定义两个指针，同时从链表的头节点出发，一个指针一次走一步，另一个指针一 次走两步。如果走得快的指针追上了走得慢的指针，那么链表就包含环；如果走得快的指针走到了链表的末尾 (m_pNext 指向 NULL) 都没有追上第一个指针，那么链表就不包含环。

第二步是如何找到环的入口。先定义两个指针P₁和P₂指向链表的头节点。如果链表中的环有n个节点，则指针P₁先在链表上向前移动 n步，然后两个指针以相同的速度向前移动。当第二个指针指向环的入口节点时，第一个指针己经围绕着环走了一圈，又回到了入口节点。

image.png

1. 指针P₁和P₂在初始化时都指向链表的头节点。

2. 由于环中有4个节点，所以指针P₁先在链表上向前移动4步。

3. 指针P₁和P₂以相同的速度在链表上向前移动，直到它们相遇。它们相遇的节,点就是环的入口节点。

struct ListNode {
    int m_nValue;
    ListNode* m_pNext;
};

// 在链表中存在环的前提下找到一快一慢两个指针相遇的节点
ListNode* MeetingNode(ListNode* pHead)
{
    if(pHead == nullptr)
        return nullptr;

    ListNode* pSlow = pHead->m_pNext;
    if(pSlow == nullptr)
        return nullptr;

    ListNode* pFast = pSlow->m_pNext;
    while(pFast != nullptr && pSlow != nullptr)
    {
        if(pFast == pSlow)
            return pFast;

        pSlow = pSlow->m_pNext;

        pFast = pFast->m_pNext;
        if(pFast != nullptr)
            pFast = pFast->m_pNext;
    }

    return nullptr;
}

ListNode* EntryNodeOfLoop(ListNode* pHead)
{
    ListNode* meetingNode = MeetingNode(pHead);
    if(meetingNode == nullptr)
        return nullptr;

    // 得到环中结点的数目
    int nodesInLoop = 1;
    ListNode* pNode1 = meetingNode;
    while(pNode1->m_pNext != meetingNode)
    {
        pNode1 = pNode1->m_pNext;
        ++nodesInLoop;
    }

    // 先移动pNode1，次数为环中结点的数目
    pNode1 = pHead;
    for(int i = 0; i < nodesInLoop; ++i)
        pNode1 = pNode1->m_pNext;

    // 再移动pNode1和pNode2
    ListNode* pNode2 = pHead;
    while(pNode1 != pNode2)
    {
        pNode1 = pNode1->m_pNext;
        pNode2 = pNode2->m_pNext;
    }

    return pNode1;
}

摘抄资料：《剑指offer》