【DS】链表面试热题之环形链表及其变体

客官°小女子只卖身不卖艺 2024-04-03 10:01 74阅读 0赞

##  ##

#### 文章目录 ####

*  
 *   *  一、判断链表是不是有环
     *   *  题目描述
         *  思路分析
         *  AC代码
     *  二、链表中环的入口节点
     *   *  题目描述
         *  思路分析
         *  图示分析
         *  AC代码
     *  三、求环的长度
     *   *  思路分析
         *  代码实现

--------------------

***环形链表核心思路：***

快慢指针：同时出发，速度不同。

模板：

ListNode fast=head;
    ListNode slow=head;
    while(fast!=null&&fast.next!=null){
        
        fast=fast.next.next;
        slow=slow.next;
        if(fast==slow){
        
            //有环了，返回true/做其他操作
        }
    }

--------------------

### 一、判断链表是不是有环 ###

#### 题目描述 ####

1.给你一个链表的头节点 `head` ，判断链表中是否有环。[OJ链接][OJ]

#### 思路分析 ####

1.  如果有环，并且两者存在速度差，那在经过一定时间后，两者必会相遇。
2.  如果没有环，fast先走到最后，返回false
3.  一定要后判断是不是相遇了，否则只要链表有值就过不了（相当于head和head）

#### AC代码 ####

public boolean hasCycle(ListNode head) {
        
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
        
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
        
                return true;
            }
        }
        return false;
    }

### 二、链表中环的入口节点 ###

#### 题目描述 ####

1.给定一个链表的头节点 `head` ，返回链表开始入环的第一个节点。 *如果链表无环，则返回 `null`。*[OJ链接][OJ 1]

#### 思路分析 ####

1.  这一题可以算是是上一题的进阶，但要是求入口点的位置还需要进行一个公式的推导【起始点、入口点、相遇点的关系】
2.  设起始点到入口点距离为X，入口点到相遇点的距离是Y，假设有环，设入口点到相遇点的距离是Z
3.  由于存在速度差，设N圈之后两者相遇，等式关系由来：路程=速度\*时间，两者总是在走，所以走的时间一样；fast的速度是slow的2倍，那么fast走过的路程就是slow的2倍。
4.  X+NC+C-Z=2\*(X+C-Z)===>X=Z+(N-1)\*C这就意味着，起始点到相遇点的距离可以通过入口点到相遇点的距离算出来。当两者走一圈就相遇的时候，起始点到相遇点的距离就等于入口点到相遇点的距离。
5.  因此在相遇之后，跳出循环，再把slow拉回起点，fast和slow都走一步，两者再次相遇就是入口节点的位置。

#### 图示分析 ####

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3MAIa4kn-1665138694005)(F:\\typora插图\\image-20221007182047166.png)\]][img-3MAIa4kn-1665138694005_F_typora_image-20221007182047166.png]

#### AC代码 ####

public ListNode detectCycle(ListNode head) {
        
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
        
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
        //相遇了，但是是两个都在相遇点，题目要求的是入口点
                break;//找到有环的部分了
            }
        }
        //2种情况——循环条件不满足、遇到break
        if(fast==null||fast.next==null){
        
            return null;//没环
        }
        slow=head;
        while(slow!=fast){
        
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }

### 三、求环的长度 ###

#### 思路分析 ####

1.  由于X=Z，所以起始点到两者从第一次相遇的地方就是环的长度

#### 代码实现 ####

public int countCycleLen(ListNode head) {
        
        int count=0;
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
        
            fast=fast.next.next;
            slow=slow.next;
            count++;
            if(fast==slow){
        //相遇了，但是是两个都在相遇点，题目要求的是入口点
                return count;//找到有环的部分了
            }
        }
        return 0;
    }

[OJ]: https://leetcode.cn/problems/linked-list-cycle/description/
[OJ 1]: https://leetcode.cn/problems/linked-list-cycle-ii/description/
[img-3MAIa4kn-1665138694005_F_typora_image-20221007182047166.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/85f166cefc174dee8d18a6fccfc3ab4b.png