解题思路

1. 使用哈希表构建链表

• 由于输入顺序可能 无序，需 先存储所有节点。
• 用 哈希表 nodes 存储 {addr: (val, next_addr)}。
• 找到 头节点 head_addr（输入第一行的 addr）。
• 按照 next_addr 顺序重建链表。

2. 使用快慢指针判断环

1. 慢指针 slow：每次移动 1 步。
2. 快指针 fast：每次移动 2 步。

Leetcode 25.环形链表-原题链接

题目描述

给定一个 单链表，其输入格式为 (地址, 值, 下一个地址) 的三元组，判断链表是否存在 环。

• 如果存在环，返回 true。
• 如果不存在环，返回 false。

输入格式

• 第一行输入一个整数 n，表示链表的 节点数。（0 ≤ n ≤ 10⁴）

• 接下来的 n 行，每行包含 三个整数：

  • addr：当前节点的 地址（唯一标识）。
  • val：当前节点的 值（-10⁵ ≤ val ≤ 10⁵）。
  • next_addr：当前节点的 下一个节点地址：
    • 若 next_addr = -1，表示链表结束。
    • 若 next_addr 指向某个 addr，表示连接到该地址，可能形成 环。

• 特别规定：

  • 第一行的 addr 永远是 head（链表头）。
  • 其余节点的顺序可以是 任意顺序，需要 按照 next_addr 构建链表。

输出格式

• 输出 true 或 false，表示链表是否存在环。

样例 1

输入

4
100 3 200
200 2 300
300 0 400
400 -4 200

输出

true

说明：

• 链表结构：

  100 -> 200 -> 300 -> 400
            ^         |
            |_________|
  

• 尾节点 400 连接到 200 形成环。

样例 2

输入

2
100 1 200
200 2 -1

输出

false

说明：

• 链表结构：

  100 -> 200 -> NULL
  

• 无环，返回 false。

样例 3

输入

1
100 1 -1

输出

false

说明：

• 单个节点，无环，返回 false。