数据结构每日一题|判断链表环形结构并返回环的起始节点

仅记录做题思路 题目均来自力扣

//找出环形的起始节点
 struct ListNode* detectCycle(struct ListNode* head) {
     ListNode* fast = head;//快指针 每次走两步
     ListNode* slow = head;//慢指针 每次走一步
    
     while (fast != NULL && fast->next != NULL)  //排除输入为空节点的情况
     {
         fast = fast->next->next;
         slow = slow->next;
         if (fast == slow)//这里找到了快慢指针的相遇点，
         {
             ListNode* sloww = head;//最后登场的指针
             while (slow != sloww) //从此开始找慢指针和超慢指针的相遇点
             {
                 sloww = sloww->next;
                 slow = slow->next;
             }
             return sloww;
         }
     }
     return NULL;
 }

怎么判断是否存在环形结构请查看上一篇文章，这里只讨论找环形结构的起始节点

思路：先将问题形象化，以下是变化的过程

初始的假设条件：快指针的移动速度为每次2节点，慢指针为1节点 

然后设

进入节点前的路程为a

慢指针进入节点后走了  b  与快指针相遇

环的一圈减去b剩下的设为 c

快指针走了   n圈+b  = n（b+c）+b 与慢指针相遇

可得关系式  a+（b+c）× n+b  = 2×（a+b）

化简得 a = n ×（ b+c ）—b

结合图理解

如果能求出a，就相当于求得了环的起始节点（用一个新的指针从起始头节点遍历a个距离的节点）

看式子的右边

我们假设快慢指针相遇后，慢指针此时从相遇点开始新的旅程，同时一个新的和他速度一样的每次走一个节点的指针从起始位置出发，当慢指针走完n圈再减去b就回到了环的起始节点，因为速度一样，所以等于 新的指针走过来的a

结合以上条件即可写出代码求解

 

原文地址：https://blog.csdn.net/2201_75446108/article/details/144017103

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！