142.环形链表II

野性酷女 2024-03-17 20:42 77阅读 0赞

#### 142.环形链表II ####

*  题干背景
 *  重要思路
 *  代码实现

## 题干背景 ##

[力扣入口-142.环形链表II][-142._II]

题意： 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。  
![在这里插入图片描述][1ebb1ffe5fe94f01b6c5739d508e4295.png]

## 重要思路 ##

1.  结论需要记住，数学证明这种步长一个为2一个为1的，快追上慢的时候，快多跑了一圈。
2.  结论需要记住，数学证明从出发点到环形入口的距离和相遇点到环形入口的距离相等。
3.  注意外层循环终止条件包括两个，并且另一个是fast.next，不要写成fast.next.next了。其中是一次两个的往前走。
4.  最后返回index1或者index2都是可以的。

## 代码实现 ##

// 142.环形链表
    public ListNode detectCycle(ListNode head){
        
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
        
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
         // 有环
                ListNode index1 = fast;
                ListNode index2 = slow;
                while(index1 != index2){
        
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;
    }

**参考资料**：[142.环形链表II][142._II]

[-142._II]: https://leetcode.cn/problems/linked-list-cycle-ii/
[1ebb1ffe5fe94f01b6c5739d508e4295.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/41cc7dcb5bae4589a2277f57554d9b1d.png
[142._II]: https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html#_142-%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8ii