牛客-链表中环的入口节点(Java)

待我称王封你为后i 2023-10-04 12:59 64阅读 0赞

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

**【题目描述】**  
对于一个给定的链表，返回环的入口节点，如果没有环，返回null

【思路】

1.  首先判断有没有环

*  我们可以设置两个指针求解此问题：一个快指针fast，每次向前走两个节点，一个慢指针low，每次向前走一个节点；我们首先需要知道一个结论：这两个指针一快一慢向前走，若链表有环，则两个指针一定会相遇；

do{
        
           fast = fast.next;
           if(fast == null)
               return null;
           fast = fast.next;
           
           low = low.next;
       }while(fast != null && fast != low);
       if(fast == null)
          return null;

*  如果循环结束fast是null则证明链表中无环，直接返回null，否则进行下一步

1.  确定环的入口节点

> 分析：可以先设置变量a表示头节点到入口节点的距离，b表示入口节点到快慢指针相遇点的距离，c表示相遇点到相遇点沿着运动方向到入口节点的距离，如图所示

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NDA4Mzkw_size_16_color_FFFFFF_t_70]

*  所以，链表的长度 = a + b + c，而环的长度就是b+c
 *  当两指针相遇时，慢指针low走过的距离为**a+b**，而快指针fast走过的距离为**a + k×(b+c) + b**，其中k是一个整数，且k>0（因为如果k==0，那快慢指针走过的距离就相等了）
 *  快指针fast每次前进两个节点，而慢指针low每次前进一个节点
 *  结论：相同时间内，快指针的走的路程是慢指针的两倍
 *  所以：可以得到 2×(a+b) == a + k × (b+c) + b  
    化简可得

2×(a+b) = a + k × (b+c) + b;
    2a + 2b = a + k × (b+c) + b
    a + b = k × (b+c)
    a = k × (b+c) - b
    a = (k-1) × (b+c) + c

*  最终结果为\*\*：a = (k-1) × (b+c) + c\*\*， 通过次公式我们可以理解从链表头节点到环入口节点的距离，等于环长度的k-1倍，再加上从相遇点到环入口节点的距离
 *  由此此题便迎刃而解： 通过第一步两个指针相遇，由此我们将设立一个指针指向链表头节点，另一个指针指向相遇点，两个指针速度均为1，沿着链表前进，最后它们相遇的位置，就是环入口节

AC代码：

public class Solution {
        
        public ListNode detectCycle(ListNode head) {
        
            if(head == null)
                return null;
            ListNode fast = head;
            ListNode low = head;
            
            do{
        
                fast = fast.next;
                if(fast == null)
                    return null;
                fast = fast.next;
                
                low = low.next;
            }while(fast != null && fast != low);
            
            if(fast == null)
                return null;
            low = head;
            while(low!=fast){
        
                fast = fast.next;
                low = low.next;
            }
            return low;
            
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NDA4Mzkw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210510110401703.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NDA4Mzkw,size_16,color_FFFFFF,t_70