剑指offer - 链表中环的入口节点

题目

如果一个链表中包含环，如何找出环的入口节点？例如：在下图所示的链表中，环的入口节点是节点3

1.png

分析

• 1、如何确定一个链表中包含环？

可以使用两个指针来解决这个问题。定义两个指针，同时从头结点出发，一个指针一次走一步，一个指针一次走两步。如果走的快的指针追上了走的慢的指针，那么链表就包含环；如果走的快的指针走到链表末尾（m_pNext为NULL）都没有追上第一个指针，那么链表就不包含环

• 2、如何找到环的入口？

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

2.png

由图可知

1、指针P1和P2在初始化时都指向链表的头结点
2、由于环中有4个结点，所以指针P1先在链表上向前移动4步
3、指针P1和P2以相同的速度在链表上向前移动，直到它们相遇，相遇的结点就是环的入口

• 3、如何得到环中结点的数量？

在前面提到判断一个链表里是否有环时用到了一块一慢的两个指针，如果两个指针相遇，则表明链表中存在环。两个指针相遇的结点一定是在环中。可以从这个结点出发，一边继续向前移动一边计数，当再次回到这个结点时，就可以得到环中结点数了

算法实现

定义链表

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

MeetingNode函数在链表中存在环的前提下找到一块一慢两个指针相遇的结点

// 是否有环
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;
}

断链法

时间复杂度为O（n）

两个指针，一个在前面，另一个紧邻着这个指针，在后面。 两个指针同时向前移动，每移动一次，前面的指针的next指向NULL。 也就是说：

访问过的节点都断开，最后到达的那个节点一定是尾节点的下一个， 也就是循环的第一个。

这时候已经是第二次访问循环的第一节点了，第一次访问的时候我们已经让它指向了NULL， 所以到这结束。但是这种方法修改了链表的指向

算法实现

ListNode * EntryNodeOfLoop2(ListNode *pHead) {
    if (pHead == nullptr ||pHead->m_pNext == nullptr)
        return nullptr;

    // 下一个结点
    ListNode *previuosNode = pHead;
    // 当前结点
    ListNode *currentNode = pHead->m_pNext;

    // 是否有环认证，无环返回
    if (MeetingNode(pHead) == nullptr)
        return nullptr;

    // 确保有环的前提之下才行，如果本身无环，那么程序执行失败。
    while (currentNode != nullptr) {
        previuosNode->m_pNext = nullptr;
        previuosNode = currentNode;
        currentNode = currentNode->m_pNext;
    }

    return previuosNode;
}

使用集合

这里用到了STL中的set，set有一个特性就是不能插入相同元素，这样只需遍历原List一次就可以判断出有没有环，还有环的入口地址。s.insert(node).second这里在插入的同时也判断了插入是否成功，如果不成功表明set中已经有该元素了，该元素就是环的入口元素。

ListNode* EntryNodeOfLoop3(ListNode* pHead)
{
    set<ListNode*> set;
    ListNode* node = pHead;
    while(node!= NULL){
        if(set.insert(node).second)
            node = node->m_pNext;
        else
            return node;
    }
    return node;
}

参考

《剑指offer》
链表中环的入口结点