链表问题_链表中环的入口节点

矫情吗；* 2022-05-21 07:23 211阅读 0赞

题目：一个链表中包含环路，求链表的入口节点。  
分析：根据求[链表中倒数第K个节点][K]的方法，这个问题可以分为两个步骤：1、判断链表中的节点个数记为K，对于这个可以采用一快一慢两个指针，当两个指针相遇时，则相遇的节点就在环中，然后根据此节点就可以求出环的大小。2、由于已经知道环的个数，就可以使用类似于求链表倒数第K个节点的方法，使用两个指针，他们之间的间隔为K，两个同时在链表上移动，当他们相遇时的节点，就为链表的入口节点。  
实现如下：

struct ListNode {
           int val;
            struct ListNode *next;
            ListNode(int x) :
                  val(x), next(NULL) {
            }
      };
    
    //找出环中的一个节点
    ListNode* OneNodeInLoop(ListNode*phead)
    {
        if(!phead)
            return NULL;
        if(!phead->next)
            return NULL;
        ListNode* pslow=phead->next;
        ListNode* pfast=pslow->next;
        while( pslow && pfast)
        {
            if(pslow==pfast)
                return pfast;
            pslow=pslow->next;
            if(pfast=pfast->next)
                pfast=pfast->next;
        }
        return NULL;
    }
    
    //链表中环的入口节点
    ListNode* EntryNodeOfLoop(ListNode* phead)
    {
        ListNode*NodeInloop=OneNodeInLoop(phead);
        if(!NodeInloop)
            return NULL;
        ListNode*pnode=NodeInloop;
        int length_of_loop=1;
        while(pnode->next!=NodeInloop)   //求出环的大小
        {
            ++length_of_loop;
            pnode=pnode->next;
        }
    
        //间隔为length_of_loop的两个指针
         ListNode* pnode_Aheind = phead;
         ListNode* pnode_Behind = phead;
         for (int i = 0; i < length_of_loop; ++i)
         {
             pnode_Aheind = pnode_Aheind->next;
         }
    
         while (pnode_Behind!= pnode_Aheind)
         {
             pnode_Aheind = pnode_Aheind->next;
             pnode_Behind = pnode_Behind->next;
         }
    
         return pnode_Behind;
    
    }

[K]: https://blog.csdn.net/xc13212777631/article/details/80831207