【链表OJ 10】环形链表Ⅱ(求入环节点)

前言:

💥🎈个人主页:​​​​​​Dream_Chaser～ 🎈💥

✨✨刷题专栏:http://t.csdn.cn/UlvTc

⛳⛳本篇内容:力扣上链表OJ题目

leetcode142. 环形链表 II

来源:
142. 环形链表 II - 力扣（LeetCode）

1.问题描述

** 给定一个链表的头节点

head

，返回链表开始入环的第一个节点。 *如果链表无环，则返回

null

---

​

题解接口：

struct ListNode *detectCycle(struct ListNode *head) {
   
}

2.代码思路

前提条件：

是fast走的路程是slow的2倍。

解题思路:

** 第一步,先定义一个快指针fast以及一个慢指针slow,**这里跟环形链表1的快慢指针的操作一致，不作详细说明。之后找到可以证明链表带环的相遇点，并定义meet指针指向slow或此时的fast。

​

  ** 第二步**:**接着让head指针从链表第一个节点开始移动，meet指针从相遇点开始移动，然后它们将会在链表带环的入口处相遇。(**这是这道题思考的方向，但是如何去证明呢？)

​

代码实现:

struct ListNode *detectCycle(struct ListNode *head) {
   struct ListNode* fast=head,*slow=head;
   while(fast&&fast->next)
   {
       slow=slow->next;
       fast=fast->next->next;
    //带环(如果条件成立，则证明该链表为带环链表)
    if(slow == fast) 
    {
    struct ListNode*meet=slow;  
    //求入环点 
    while(head!=meet)
    {
        head=head->next;
        meet=meet->next;
    }
        return meet;//返回链表开始入环的第一个节点
    }
    }
    return NULL;//如果链表无环，则返回 null
}

代码执行:

​

3.问题分析

结论证明:

** 一个指针从相遇点(meet)走，一个指针从链表头(head)开始走，他们会在入口点(返回值)相遇。为什么?以下是证明:**

假设:

链表头--环入口点距离:L

环入口点--相遇点距离:X

环的长度:C

依据题意求出slow指针所走过的距离，明显是L+X

​

然后思考一个问题:有没有可能slow进环转了几圈才追上?

    答:**不可能! 1圈之内，fast必然追上slow，因为他们之间距离每次缩小1，不会错过，slow走1圈，fast都走了2圈了，肯定追上了。**

    所以说可以简单的求出fast指针在环上走过的距离:**L+C ＋X ** ，并且根据

    **2*(L+X) = L+C+X**

** L+X = C**

    **第一种情况****:L=C-X** -->可以求出链表头到环入口点距离

​

    试想一下,当**L**的距离越长，环的大小越小，那么**L=C-X**依旧成立吗？

​

    由图可得, 可得到**第二个结论**:**L=(n-1)*C+C-X   (n-1)*C**表示**fast**在环内转了**（n-1）**圈

    总结:无论是第一种情况，还是第二种情况，meet与head均会在入环处相遇。

    本篇到此结束，感谢你的来访与支持，如有错误，十分欢迎指正。