LeetCode 141. 环形链表

Categories:

Tags:

题目描述
思路分析
1. 解法一：快慢指针（Floyd 判环）（推荐）
2. 解法二：哈希集合
相似题目

题目描述

✅ 141. 环形链表

思路分析

解法一：快慢指针（Floyd 判环）（推荐）

核心思路：

slow 每次走 1 步，fast 每次走 2 步，同时从 head 出发。

如果存在环，fast 会在环内追上 slow；如果无环，fast 会先走到 nil。

题目只需判断是否相遇，不需要定位入口。

复杂度分析：

时间复杂度：O(n)，其中 n 表示链表节点数。

空间复杂度：O(1)，仅使用常数个指针变量。

class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }

        // 快慢指针从头结点出发
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            // 若相遇说明存在环
            if (slow == fast) {
                return true;
            }
        }

        return false;
    }
}

func hasCycle(head *ListNode) bool {
	if head == nil || head.Next == nil {
		return false
	}

	// 快慢指针从头结点出发
	slow, fast := head, head

	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next

		// 若相遇说明存在环
		if slow == fast {
			return true
		}
	}

	return false
}

解法二：哈希集合

核心思路：

遍历链表时将节点指针加入集合。

若遇到已存在的节点，说明出现重复访问，即存在环。

复杂度分析：

时间复杂度：O(n)，其中 n 表示链表节点数。

空间复杂度：O(n)，其中 n 表示哈希集合存储的节点数。

class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> visited = new HashSet<>();
        ListNode current = head;

        while (current != null) {
            // 已访问过则存在环
            if (visited.contains(current)) {
                return true;
            }

            visited.add(current);
            current = current.next;
        }

        return false;
    }
}

func hasCycle(head *ListNode) bool {
	visited := make(map[*ListNode]struct{})
	current := head

	for current != nil {
		// 已访问过则存在环
		if _, ok := visited[current]; ok {
			return true
		}

		visited[current] = struct{}{}
		current = current.Next
	}

	return false
}

相似题目

题目	难度	考察点
142. 环形链表 II	中等	Floyd 判环
287. 寻找重复数	中等	快慢指针
202. 快乐数	简单	快慢指针、哈希表
876. 链表的中间结点	简单	快慢指针
160. 相交链表	简单	双指针
234. 回文链表	简单	快慢指针

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/13009476