題目描述

給定一個(gè)鏈表，判斷鏈表中是否有環(huán)，存在環(huán)返回 true，否則返回 false

• 連續(xù)跟蹤 next 指針再次到達(dá)某個(gè)節(jié)點(diǎn)，則鏈表中有環(huán)
• 你能用 O(1)（即，常量）內(nèi)存解決此問(wèn)題嗎？

提示：
鏈表中節(jié)點(diǎn)的數(shù)目范圍是 [0, 10^4]
-10^5 <= Node.val <= 10^5
pos 為環(huán)開(kāi)始節(jié)點(diǎn)的索引，若 pos = -1，則沒(méi)有環(huán)
pos 為 -1 或者鏈表中的一個(gè) 有效索引
pos 不作為參數(shù)進(jìn)行傳遞，僅僅是為了標(biāo)識(shí)鏈表的實(shí)際情況

注意：pos 只是幫助理解測(cè)試用例，并不是真正的輸入值

數(shù)據(jù)結(jié)構(gòu)

• 數(shù)組、指針變量

算法思維

• 遍歷、雙指針、快慢指針、追擊

解題要點(diǎn)

• 鏈表的特點(diǎn)
• 快慢指針的思想以及使用
• 模型的應(yīng)用：涉及"環(huán)"的問(wèn)題 --> 追擊問(wèn)題 --> 快慢指針

解題步驟

一. Comprehend 理解題意

可以理解為"重復(fù)訪問(wèn)"問(wèn)題，檢測(cè)鏈表的某節(jié)點(diǎn)能否二次到達(dá)

• 需要一個(gè)容器記錄已經(jīng)訪問(wèn)過(guò)的節(jié)點(diǎn)
• 每次訪問(wèn)到新的節(jié)點(diǎn)，都與容器中的記錄進(jìn)行匹配，若相同則存在環(huán)
• 若匹配之后沒(méi)有相同節(jié)點(diǎn)，則存入容器，繼續(xù)訪問(wèn)新的節(jié)點(diǎn)
• 直到訪問(wèn)節(jié)點(diǎn)的next指針?lè)祷豱ull，或者當(dāng)前節(jié)點(diǎn)與容器的某個(gè)記錄相同，操作結(jié)束

也可以理解為“追擊”問(wèn)題，如果存在環(huán)，跑得快的一定能追上跑得慢的

• 就像一快一慢兩個(gè)運(yùn)動(dòng)員，如果在直道賽跑，不存在追擊問(wèn)題；
  如果是在環(huán)道賽跑，快的繞了一圈肯定可以追上慢的
• 定義快慢兩個(gè)運(yùn)動(dòng)員，指向鏈表的第一、第二個(gè)節(jié)點(diǎn)：slow = head; fast = head.next;
• 快運(yùn)動(dòng)員的步長(zhǎng)為2，慢的為1，即fast每次移動(dòng)兩個(gè)節(jié)點(diǎn)，slow每次移動(dòng)一個(gè)節(jié)點(diǎn)
• 若最終 fast == slow ，說(shuō)明存在環(huán)；若 fast == null || fast.next == null，操作結(jié)束

二. Choose 選擇數(shù)據(jù)結(jié)構(gòu)與算法

解題方法

• 解法一：二次到達(dá)法
• 解法二：追擊問(wèn)題法

解法一：二次到達(dá)法

數(shù)據(jù)結(jié)構(gòu)：數(shù)組（或者：鏈表、棧、隊(duì)列）
算法思維：遍歷

解法二：追擊問(wèn)題法

數(shù)據(jù)結(jié)構(gòu)：指針變量 x 2
算法思維：遍歷、雙指針（快慢指針）

三. Code 編碼實(shí)現(xiàn)基本解法

解法一：二次到達(dá)法 -- 思路分析

1. 定義數(shù)組記錄已訪問(wèn)節(jié)點(diǎn)：new ListNode[10000];
2. 遍歷鏈表的每個(gè)節(jié)點(diǎn)，并與容器中已存放的節(jié)點(diǎn)依次比較：
   ? 相同則方法結(jié)束，返回 true
   ? 不同則存入最新位置，繼續(xù)遍歷下個(gè)節(jié)點(diǎn)
3. 若 next 指針為 null，則方法結(jié)束，返回 false

邊界問(wèn)題

• 數(shù)組越界：
  鏈表最多有一萬(wàn)個(gè)節(jié)點(diǎn)，容器不會(huì)越界；
  與容器中節(jié)點(diǎn)進(jìn)行比對(duì)，正向遍歷容器，元素為 null 時(shí)終止，后續(xù)都是未使用的空間

細(xì)節(jié)問(wèn)題

• 遍歷鏈表，通過(guò) head=head.next 進(jìn)行迭代
  當(dāng)且僅當(dāng)此節(jié)點(diǎn)與容器某個(gè)節(jié)點(diǎn)相同時(shí)返回 true，其它情況都返回 false
  比較相等時(shí)可以用 "=="（比較地址）

class Solution {
    public boolean hasCycle(ListNode head) {
        // 1.定義數(shù)組記錄已訪問(wèn)節(jié)點(diǎn) 
        ListNode[] array = new ListNode[10000];
        // 2.遍歷鏈表的每個(gè)節(jié)點(diǎn)， 
        while(head != null) {
            // 并與容器鐘已存放的節(jié)點(diǎn)依次比較 
            for(int i = 0; i < array.length; i++) {
                if(array[i] == head) {
                    return true;
                }
                if(array[i] == null) {
                    array[i] = head; // 將當(dāng)前節(jié)點(diǎn)存放到最新位置 
                    break; // 結(jié)束容器的遍歷 
                }
            }
            head = head.next;
        }
        // 3.若next指針為null，則方法結(jié)束，返回false
        return false;
    }
}

時(shí)間復(fù)雜度：O(n²) -- 遍歷數(shù)組 O(n)，每個(gè)節(jié)點(diǎn)都需要額外再遍歷一次數(shù)組 O(n²)
空間復(fù)雜度：O(1) -- 固定長(zhǎng)度 10000 的數(shù)組 O(1)
執(zhí)行耗時(shí)：108 ms，擊敗了 5.26% 的Java用戶
內(nèi)存消耗：38.3 MB，擊敗了 99.89% 的Java用戶

四. Consider 思考更優(yōu)解

剔除無(wú)效代碼，優(yōu)化空間消耗

• 每個(gè)節(jié)點(diǎn)都需要遍歷容器查找，比較耗時(shí)
• 按最大測(cè)試數(shù)據(jù)量創(chuàng)建容器，空間消耗巨大

尋找更好的算法思維

• 要證明某個(gè)節(jié)點(diǎn)是否第二次到達(dá)，可否將已遍歷節(jié)點(diǎn)進(jìn)行標(biāo)記？
• 環(huán)形結(jié)構(gòu)對(duì)應(yīng)生活中的追擊問(wèn)題，可否使用“追擊問(wèn)題”模擬實(shí)現(xiàn)？
• 借鑒其它算法

五. Code 編碼實(shí)現(xiàn)最優(yōu)解

解法二：追擊問(wèn)題法 -- 思路分析

1. 定義快慢兩個(gè)指針：slow = head; fast = head.next;
2. 遍歷鏈表：
   ? 快指針步長(zhǎng)為 2：fast = fast.next.next;
   ? 慢指針步長(zhǎng)為 1：slow = slow.next;
3. 當(dāng)且僅當(dāng)快慢指針重合，有環(huán)，返回 true
4. 快指針為 null，或其 next 指向 null，沒(méi)有環(huán)，返回 false，操作結(jié)束

邊界問(wèn)題

• fast 和 fast.next 指針的非空判斷
• slow.next 指針不需要非空判斷
  若有環(huán)，則始終有：slow.next != null
  若無(wú)環(huán)，則 fast 或 fast.next 先為空

細(xì)節(jié)問(wèn)題

• 需要注意：由于 fast 的步長(zhǎng)為 2，因此 fast == null 和 fast.next == null 都需要判斷

class Solution {
    public boolean hasCycle(ListNode head) {

        //0.非空判斷
        if (head == null) return false;

        //1.聲明快慢兩個(gè)指針
        ListNode slow = head;
        ListNode fast = head.next;

        //2.利用短路特性，先判斷 fast 是否為空，再判斷 fast.next 是否為空
        while (slow != fast && fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow == fast;
    }
}

時(shí)間復(fù)雜度：O(n) -- 遍歷鏈表 O(n)
空間復(fù)雜度：O(1) -- 兩個(gè)指針變量 O(1)
執(zhí)行耗時(shí)：0 ms，擊敗了 100% 的Java用戶
內(nèi)存消耗：38.8 MB，擊敗了 88.78% 的Java用戶

六. Change 變形與延伸

題目變形

• （練習(xí)）分別使用 head 和 head.next 作為鏈表的 快/慢 指針
• （練習(xí)）標(biāo)記值法：對(duì)節(jié)點(diǎn)的 val 屬性進(jìn)行標(biāo)記，賦一個(gè)超出合法范圍的值
• （練習(xí)）hash 表法

延伸擴(kuò)展

• 龜兔賽跑問(wèn)題，追擊問(wèn)題
• 地球，火星與太陽(yáng)連為一線的問(wèn)題