锻练编程思维——每日一题：《剑指offer》链表中环的入口结点

「爱情、让人受尽委屈。」 2023-02-14 07:49 47阅读 0赞

### 目录 ###

*  题目描述
 *  题目分析
 *  题解代码
 *  注意

# 题目描述 #

题目描述  
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。  
题目给出的代码框架

/*
    struct ListNode {
        int val;
        struct ListNode *next;
        ListNode(int x) :
            val(x), next(NULL) {
        }
    };
    */
    class Solution {
        
    public:
        ListNode* EntryNodeOfLoop(ListNode* pHead)
        {
        
    
        }
    };

# 题目分析 #

采用双指针法，整体思路是判断链表是否有环存在—计算环中结点个数—数学方法计算出链表的环的入口节点  
具体思路：  
（不需要异常处理，会在下面说明为什么）

*  ①判断链表有无环的具体思路和操作
    
     *  **定义快慢指针并将其初始化为和链表头指针一样指向链表首元结点**，快指针一次走两个结点，慢指针一次走一个结点
     *  快指针因为走得快，所以要**判断快指针指向是否涉及到空结点或者其指向结点的next域是否为空结点，这个作为循环条件**，因为判断链表有无环是需要不断迭代快慢指针。
     *  定义一个布尔变量flag，**当flag=false代表链表无环，flag=true代表链表有环**。
     *  因为快指针指向首元结点（和头指针指向一样），所以头指针指空结点意味着快指针一开始被初始化为指空结点，也就意味着该链表是空表（空表肯定无环），flag=false，这样就跳过判断链表有无环的循环，直接走`if(!flag){return NULL;}`，所以**异常处理可以和判断出链表无环的情况合并**
     *  **快慢指针迭代，若快慢指针再次相等(if(快指针==慢指针）放入循环里，这样每一次迭代都会判断if的条件是否成立），让flag=true后break出循环，证明链表有环；如果快指针指向了空结点或其指向结点的next域为空结点（因为快指针一次走俩结点，所以循环条件是这么个条件），证明链表无环（flag=false不会因此改变）。**
     *  循环结束后判断flag，等于false链表无环，等于true链表有环。  
        第一部分思路的代码

ListNode *fast=pHead,*low=pHead;//定义快慢指针（注意定义为结构体指针。。。
            //所以要写结构体指针->next而非结构体指针.next）
            bool flag=false;//用来判断快慢指针是否重合来进一步决定是否链表有环
            while(fast!=NULL&&fast->next!=NULL)
            {
        
                low=low->next;
                fast=fast->next->next;
                //快指针一次走两个结点，慢指针一次走一个结点
                //这样才能称为快慢指针（用来判断环是否存在）
                if(fast==low)
                {
        
                    flag=true;
                    break;
                    //当快慢指针指向了一个结点，证明链表有环
                    //不用再让快慢指针遍历链表来判断链表是否
                    //有环了
                }
            }
            if(!flag)
            {
        
                return NULL;
                //flag=true,链表有环，不用走if里，否则
                //（flag=false），链表无环，走if直接return null
                //说明链表无环
            }

*  ②记录环中结点个数
    
     *  如果链表有环，设立一个**统计环中结点个数**的变量num，赋初值1，然后**让快指针充当遍历环的指针**，即快指针=快指针->next，做好下次迭代的准备
     *  进入循环，num++，来统计环中结点个数，然后让遍历指针（快指针）迭代，当快慢指针再次相遇证明统计环中结点个数完毕。

int num=1;//num用来记录环中结点个数，为后面的使用数学技巧得出链表的环的入口节点做准备
            fast=fast->next;//fast指针充当遍历环的指针
            //记录环中结点的个数
            //low指针别动，做一个标杆，快慢指针相等预示着环遍历完了
            //这样就记录了环中结点个数
            while(fast!=low)
            {
        
                num++;//记录了一个环中结点就让遍历指针指向下一个结点
                fast=fast->next;
            }
            fast=low=pHead;//让快慢指针重新指向头结点
            //这时需要点数学技巧（把链表包括其环铺平然后快慢指针走等长步
            //）如果快慢指针相遇即为环入口结点（因为快指针和慢指针相遇
            //一定代表快指针绕环走一圈走到环的入口了又）
            //，来找寻链表的环的入口节点
            //数学技巧如上图

*  ③数学技巧找到链表环的入口结点
    
     *  让快慢指针重新指向链表首元结点（和头指针指向再次一样），**让r先走num个结点，然后快慢指针迭代速度一致（同步前进），当快慢指针再次相遇（即迭代相同次），证明找到环的入口节点，如图所示**，然后返回慢指针或者快指针即可（因为返回类型是结构体指针类型，也间接返回链表中环的入口结点）  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70]  
        第三部分思路代码：

for(int i=0;i<num;i++)
            {
        
                fast=fast->next;//快指针先走n个结点
            }
            while(fast!=low)
            {
        
                low=low->next;
                fast=fast->next;//快慢指针同步走
                //直到快慢指针相遇，相遇处即为链表的环的入口节点
                
            }
            return low;//快慢指针相遇，他们指向的结点就是链表中环的入口结点
            //返回快指针或慢指针都行，因为该函数返回类型是一个结构体指针类型

# 题解代码 #

/*
    struct ListNode {
        int val;
        struct ListNode *next;
        ListNode(int x) :
            val(x), next(NULL) {
        }
    };
    */
    class Solution {
        
    public:
        ListNode* EntryNodeOfLoop(ListNode* pHead)
        {
        
            
            ListNode *fast=pHead,*low=pHead;//定义快慢指针（注意定义为结构体指针。。。
            //所以要写结构体指针->next而非结构体指针.next）
            bool flag=false;//用来判断快慢指针是否重合来进一步决定是否链表有环
            while(fast!=NULL&&fast->next!=NULL)
            {
        
                low=low->next;
                fast=fast->next->next;
                //快指针一次走两个结点，慢指针一次走一个结点
                //这样才能称为快慢指针（用来判断环是否存在）
                if(fast==low)
                {
        
                    flag=true;
                    break;
                    //当快慢指针指向了一个结点，证明链表有环
                    //不用再让快慢指针遍历链表来判断链表是否
                    //有环了
                }
            }
            if(!flag)
            {
        
                return NULL;
                //flag=true,链表有环，不用走if里，否则
                //（flag=false），链表无环，走if直接return null
                //说明链表无环
            }
            int num=1;//num用来记录环中结点个数，为后面的使用数学技巧得出链表的环的入口节点做准备
            fast=fast->next;//fast指针充当遍历环的指针
            //记录环中结点的个数
            //low指针别动，做一个标杆，快慢指针相等预示着环遍历完了
            //这样就记录了环中结点个数
            while(fast!=low)
            {
        
                num++;//记录了一个环中结点就让遍历指针指向下一个结点
                fast=fast->next;
            }
            fast=low=pHead;//让快慢指针重新指向头结点
            //这时需要点数学技巧（把链表包括其环铺平然后快慢指针走等长步
            //）如果快慢指针相遇即为环入口结点（因为快指针和慢指针相遇
            //一定代表快指针绕环走一圈走到环的入口了又）
            //，来找寻链表的环的入口节点
            //数学技巧如上图
            for(int i=0;i<num;i++)
            {
        
                fast=fast->next;//快指针先走n个结点
            }
            while(fast!=low)
            {
        
                low=low->next;
                fast=fast->next;//快慢指针同步走
                //直到快慢指针相遇，相遇处即为链表的环的入口节点
                
            }
            return low;//快慢指针相遇，他们指向的结点就是链表中环的入口结点
            //返回快指针或慢指针都行，因为该函数返回类型是一个结构体指针类型
            
        }
    };

# 注意 #

**C++中NULL一定大写，return NULL;**,char \*p=NULL;

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200601202318147.JPG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA==,size_16,color_FFFFFF,t_70