leetCode-142:Linked List Cycle II

问题描述

给定一个链表，要求判断链表是否存在环，如果存在环，则返回环的入口节点，否则返回 null。题目链接：**点我**

样例输入输出

输入：

输出：Node(2)

输入：1

输出：null

问题解法

此题比较简单的做法是使用一个 set 来保存遍历过的节点，如果后续第一次遇到已经遍历过的节点，那就说明这个节点是环的入口节点，否则不存在环。但是此做法需要用额外的空间来保存。

优化一点的做法是，使用快慢指针，按照判断是否存在环的做法进行查找，如果找到环，假设此时环外的链表长度为 a，环起始节点到相遇节点的距离为 b，环内相遇节点剩下的距离为 c，则存在以下表达式

slow = a + b    // 当slow指针开始进入环后，此时无论fast指针在哪，slow指针不用走一圈就能与fast指针相遇
fast = a + b + n(b + c)    // n 表示 fast 指针绕环 n 圈
fast = 2 * slow

根据上述表达式可以得出以下公式

a = (n - 1)(b + c) + c

可以看到，环外的链表距离等于相遇节点环内剩余距离加上 n - 1 圈环长度。因此，此时如果用一个指针从链表头部开始，与 slow 指针同时开始一步步遍历，最终两个指针相遇就是环的入口。

代码如下

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    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;
             }
         }

         if (fast == null || fast.next == null) {
             return null;
         }

         ListNode p = head;
         while (p != slow) {
             p = p.next;
             slow = slow.next;
         }
         
         return p;
    }
}

参考资料

https://leetcode.cn/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode-solution/