題目地址

https://leetcode-cn.com/problems/linked-list-cycle-ii/

題目描述

給定一個(gè)鏈表，返回鏈表開始入環(huán)的第一個(gè)節(jié)點(diǎn)。 如果鏈表無環(huán)，則返回 null。
為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該鏈表中沒有環(huán)。注意，pos 僅僅是用于標(biāo)識環(huán)的情況，并不會作為參數(shù)傳遞到函數(shù)中。

說明：不允許修改給定的鏈表。
進(jìn)階：
你是否可以使用 O(1) 空間解決此題？
 
示例 1：
輸入：head = [3,2,0,-4], pos = 1
輸出：返回索引為 1 的鏈表節(jié)點(diǎn)
解釋：鏈表中有一個(gè)環(huán)，其尾部連接到第二個(gè)節(jié)點(diǎn)。
示例 2：
輸入：head = [1,2], pos = 0
輸出：返回索引為 0 的鏈表節(jié)點(diǎn)
解釋：鏈表中有一個(gè)環(huán)，其尾部連接到第一個(gè)節(jié)點(diǎn)。
示例 3：
輸入：head = [1], pos = -1
輸出：返回 null
解釋：鏈表中沒有環(huán)。
 
提示：
鏈表中節(jié)點(diǎn)的數(shù)目范圍在范圍 [0, 104] 內(nèi)
-105 <= Node.val <= 105
pos 的值為 -1 或者鏈表中的一個(gè)有效索引

思路

1. 首先用快慢指針看是否有環(huán)
2. 假設(shè) head到環(huán)起點(diǎn)距離是a, a到相遇點(diǎn)距離為b，b到環(huán)起點(diǎn)距離為c。
   快慢指針相遇時(shí), 快指針走過的距離是慢指針的兩倍：
   2(a+b) = a+b+c+b;
   a=c;
   從相遇點(diǎn)再走c到環(huán)起點(diǎn)相當(dāng)于從a走到環(huán)起點(diǎn)，再拿兩個(gè)相同快慢的指針一個(gè)從head走，一個(gè)從相遇點(diǎn)走，再次相遇就是環(huán)起點(diǎn)。

題解

/**
 * @Author: vividzcs
 * @Date: 2021/2/6 10:04 下午
 */
public class DetectCycle {
    public static void main(String[] args) {
        int[] arr = {1,2};
        ListNode head = ListNode.createListNodeCycle(arr, 0);

        ListNode cycleNode = detectCycle(head);

        if (cycleNode == null) {
            System.out.println("無環(huán)");
        } else {
            System.out.println("有環(huán): " + cycleNode.getVal());
        }
    }

    private static ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        boolean hasCycle = false;
        while (slow != null && fast != null && fast.getNext() != null) {
            slow = slow.getNext();
            fast = fast.getNext().getNext();
            if (slow == fast) {
                hasCycle = true;
                break;
            }
        }
        ListNode newSlow = head;
        if (hasCycle) {
            while (newSlow != slow) {
                newSlow = newSlow.getNext();
                slow = slow.getNext();
            }
            return newSlow;
        }
        return null;
    }
}