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

题目描述：

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

思路分析：

这道题首先需要判断链表是否存在环，很快就能想到用快慢指针来判断。

由于快慢指针的相遇位置并不一定为链表环的入口结点，需要进一步判断。这里参考了一个博客 https://www.cnblogs.com/likeio/p/3593686.html ，由于快指针和慢指针相遇时，快指针一定比慢指针多走了n（n=1, 2, ...)个环，可以通过列对应关系得知，在已知有环的情况下，两个指针分别以头结点和相遇结点为起点，步长为1前进，一定会在环的入口结点相遇。

需要注意是，在找入口结点时，首先需要判断头结点和相遇结点是否相等，再进行后续判断，否则对于头结点即为入口结点的情况会遗漏。

代码：

 /*

 struct ListNode {

     int val;

     struct ListNode *next;

     ListNode(int x) :

         val(x), next(NULL) {

     }

 };

 */

 class Solution {

 public:

     ListNode* EntryNodeOfLoop(ListNode* pHead)

     {

         if(pHead==nullptr)

             return nullptr;

         ListNode* walker;

         ListNode* runner;

         walker = pHead;

         runner = pHead;

         while(walker!=nullptr && runner!=nullptr)

         {

             walker = walker->next;

             if(runner->next==nullptr)

                 return nullptr;

             else

                 runner = runner->next->next;

             if(runner==walker)

                 break;

         }

         if(walker == runner)

         {

             walker = pHead;

             while(walker!=nullptr && runner!=nullptr)

             {

                 if(runner==walker)

                     break;

                 walker = walker->next;

                 runner = runner->next;

             }

             if(walker==runner)

                 return walker;

             else

                 return nullptr;

         }

         else

             return nullptr;

     }

 };

巴特西

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

最新文章

热门文章