BM7 链表中环的入口结点

 

 审题:

        如果给出的第二个链表不为空，则一定有环。

        我们先把两种特殊情况搞定:

        {1}、{}                //无环，直接返回null

        {}、{2}               //有环，返回第二个链表任意节点

ok...好吧

我们看题目给的函数输入，只有一个参数，那么pHead是将两个链表已经链接好了。

好吧，是我想多了，看来这就是一个简单的找入环节点的问题。。。。

嘻嘻，见谅，见谅。。。。

至于为毛我要用这么通俗的话讲解，还不因为算法这个本来就比较抽象难懂，这样子表达会更容易理解和感同身受。。。呜呜，真是良苦用心，创作不易，点个关注吧，，，嘻嘻

---

如何判断有没有环:

        通过快慢指针就ok

        快指针，每次走两步，慢指针一次走一步(其实我感觉快指针只要比慢指针快就ok)

    1.假设没有环,那么是不是可以理解为两个指针从同一个起点出发，沿着一条有尽头的路向前进军

 

2.假设有环，那么怎么理解呢？

   假设有一天你偷偷出去上网，你老爸知道了，去网吧抓你。然后你跑到学校操场，停下来，你就对你爸说:“笨老头，抓不到我吧”。。。。

    你和你爸同时在同一个起点出发(都是从你网吧的座位出发)，你爸的速度是你的两倍，然后当你跑到操场，你沿着操场跑。你爸追你。是不是只要你爸速度比你快，就一定能够抓到你。怎么说呢，不晓得好理解波(如果有问题，可以私信)

 

 

 如何找到入口节点:

        根据XXX数学家，原谅我的无知，我只是知道这么个理论。。。。

        fast和last相遇的点到入环节点 与 起点到入环节点距离相同

        

---

思路分析完了，上代码

别跟我说不会写代码，慢慢调呗。。。。可以借鉴，不可以照抄

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        
        ListNode *fast = nullptr;
        ListNode *last = nullptr;
        ListNode *p = nullptr;
        if(pHead->next == nullptr || pHead->next->next == nullptr)
        {
            return p;
        }
        
        fast = pHead->next->next;
        last = pHead->next;
       
        while(1)
        {   
            if(fast == nullptr || fast == last)
            {    
                break;
            }
            if(fast->next != nullptr)
            {
                fast = fast->next->next;
            }
            else
            {
                fast = nullptr;
            }
           
            last = last->next;
        }
       
        if(fast == last)
        {
            p = pHead;
            while(1)
            {
                if(p == last)
                {
                    break;
                }
                p = p->next;
                last = last->next;
                
            }
           
        }
      
       
        return p;
    }
};

 日常吐槽:

        写题目三分钟，写博客题解十年功