【数据结构】给定一个链表，判定链表是否有环，如果有，返回链表开始入环的第一个节点，如果链表无环，则返回 null。

小鱼儿 2023-03-04 03:28 3阅读 0赞

# 1.判断链表是否有环 #

**思路：使用快慢指针解决是否有环**

假设链表是一个有环链表，设置两个指针，slow，和fast让两个指针从前往后遍历，而且fast的遍历速度是slow的两倍，如果有环的话，遍历快的fast的不会为null，并且slow一定会追上fast，fast会和slow相等，过程如下图所示：fast走两步，slow走一步

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjY5MDA3_size_16_color_FFFFFF_t_70][]

代码：

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

# 2.求出成环的位置 #

**思路：s=vt（路程 = 速度 \* 时间），用方程思想列等式解**

因为路程知道，速度知道（二倍关系），时间也知道（相等），可以列等式关系进行求解；

如下图：假设链表是Link，fast是快的指针，slow是慢的指针；

k是环的入口，p是快慢指针相遇的地方；a，b，c分别代表三段长度；

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjY5MDA3_size_16_color_FFFFFF_t_70 1][]

所以，让指针从相遇点p和起始点同时遍历，这样由于c = a所以p1和p2在k相遇，而k就是入口；

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjY5MDA3_size_16_color_FFFFFF_t_70 2][]

代码如下：

public static ListNode detectCycle(ListNode head){
            if(head == null){
                return null;
            }
            ListNode fast = head;
            ListNode slow = head;
            do{
                fast = fast.next;
                if(fast != null){
                    fast = fast.next;
                    slow = slow.next;
                }
            }while(fast != null && fast != slow);
            if(fast == null){
                return null;
            }
            ListNode p1 = head;
            ListNode p2 = slow;
            while(p1 != p2){
                p1 = p1.next;
                p2 = p2.next;
            }
            return p1;
        }

参考文章：[https://blog.csdn.net/weixin\_40879743/article/details/90646399][https_blog.csdn.net_weixin_40879743_article_details_90646399]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjY5MDA3_size_16_color_FFFFFF_t_70]: /images/20230208/271ee7e257f54bb0a5c6fc1be24a0f5b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjY5MDA3_size_16_color_FFFFFF_t_70 1]: /images/20230208/d5b6d3801cd1484ab0244610bd770ecd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjY5MDA3_size_16_color_FFFFFF_t_70 2]: /images/20230208/caa0f620460b4abdafa42d5dd97ddc46.png
[https_blog.csdn.net_weixin_40879743_article_details_90646399]: https://blog.csdn.net/weixin_40879743/article/details/90646399