Leetcode 分類刷題 —— 鏈表類（Linked List）

1、題目

Leetcode 141. Linked List Cycle (Linked List Cycle II)

給你一個(gè)鏈表的頭節(jié)點(diǎn) head ，判斷鏈表中是否有環(huán)。如果鏈表中有某個(gè)節(jié)點(diǎn)，可以通過連續(xù)跟蹤 next 指針再次到達(dá)，則鏈表中存在環(huán)。 如果鏈表中存在環(huán) ，則返回 true 。 否則，返回 false 。

2、思路

方法一：用哈希表（HashSet）存儲(chǔ)所有已經(jīng)訪問過的節(jié)點(diǎn)，每次我們到達(dá)一個(gè)節(jié)點(diǎn)：
如果該節(jié)點(diǎn)已經(jīng)存在于哈希表中，則說明該鏈表是環(huán)形鏈表，否則就將該節(jié)點(diǎn)加入哈希表中。
方法二：快慢指針若相遇則判斷有環(huán)：適用于鏈表中獲取倒數(shù)第k個(gè)元素、獲取中間位置的元素、
判斷鏈表是否存在環(huán)、判斷環(huán)的長(zhǎng)度等和長(zhǎng)度與位置有關(guān)的問題。

3、快慢指針 Java 代碼

public class Solution {
    public boolean hasCycle(ListNode head) {
        // 空鏈表、單節(jié)點(diǎn)鏈表一定不會(huì)有環(huán)
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}

參考文章：
https://leetcode.cn/problems/linked-list-cycle/solution/huan-xing-lian-biao-by-leetcode-solution/