牛客网剑指offer刷题练习之链表中环的入口结点

​​作者简介：C/C++领域新星创作者，为C++和java奋斗中
个人社区：微凉秋意社区
系列专栏：剑指offer刷题
推荐一款模拟面试、刷题神器注册免费刷题

前言

今天分享用C++做算法题的经验，题目来自于牛客网《剑指offer》专栏里的一道中等难度的链表题，用到了快慢指针的思想。当然除了快慢指针也用到了其他的数学思想，感兴趣的小伙伴快来看看吧！

活动地址：CSDN21天学习挑战赛

链表中环的入口结点问题

一、题目描述

输出示例：

二、题目解析

1、解题思路

解题思路分为两部分：

1. 遇到链表中环的问题优先考虑双指针里的快慢指针，快指针就是一次走两个路径，慢指针则只走一个路径，只要快慢指针相遇就返回该结点位置。只要链表中存在环，那么快慢指针必定会相遇。
2. 快指针从头开始，慢指针从相遇点开始，二者同时开始走，再次相遇时的位置必定是环的入口处。

2、证明结论

• 必定会相遇

设置快慢指针fast和low，fast每次走两步，low每次走一步。假如有环，两者一定会相遇(因为low一旦进环，可看作fast在后面追赶low的过程，每次两者都接近一步，最后一定能追上)。

• 必定是环的入口处

链表头到环入口长度 —— a
环入口到相遇点长度为——b
相遇点到环入口长度为——c

当fast与slow相遇时，fast走过的距离为a + k(b + c) + b，而slow走过的距离为a + b，因为fast是slow速度的两倍，则有a+k(b + c)+b = 2*(a+b)，化简得出a=b(k-1)+kc;此时slow节点在相遇点，由表达式可以看出当k为一时，a=c，那么我们让快指针从起点开始走，刚好可以让快慢指针在环入口处相遇。(k是fast走过的环数)

三、代码实现与解释

1、题目源码

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; */
class Solution {
    
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
    
        ListNode* slow=flpointer(pHead);
        if(slow==NULL)
            return NULL;
        ListNode* fast=pHead;
        while(fast!=slow){
    
            fast=fast->next;
            slow=slow->next;
        }
        return slow;
    }
    ListNode* flpointer(ListNode* head){
    
        if(head==NULL)
            return NULL;
        ListNode* fast=head;
        ListNode* slow=head;
        while(fast!=NULL&&fast->next!=NULL){
    
            fast=fast->next->next;
            slow=slow->next;
            if(slow==fast)
                return slow;
        }
        return NULL;
    }
};

2、重要代码解释

ListNode* flpointer(ListNode* head) 这个函数的作用是找到快慢指针的相遇点。先考虑并处理链表为空的情况，然后定义快慢指针，当快指针对应的结点以及相邻结点不为空时让快指针走两步，慢指针走一步，直到二者相等返回结点位置。

ListNode* EntryNodeOfLoop(ListNode* pHead) 这个函数的作用就是调用上面flpointer函数并解决问题。当存在快慢指针相等情况时，让快指针从头开始走，与相遇时同时进行，只要相遇就返回结点，这个结点位置就是环入口。

写在最后
有关链表环的题目大都是和双指针有关，认真的做一道题比盲目刷几十道收获要大得多，勤做笔记，善于用思考才会变强！让我们一起刷题，提升自己吧!!!

​