解题思路

1. 使用哈希表构建链表

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

2. 使用快慢指针判断环

1. 慢指针 slow：每次移动 1 步。
2. 快指针 fast：每次移动 2 步。
3. 如果 fast 追上 slow，说明有环，返回 true。
4. 如果 fast 遇到 NULL，说明无环，返回 false。

时间复杂度： ( O(n) )
空间复杂度： ( O(n) )（哈希表存储所有地址）

代码实现

C++ 版本

#include <iostream>
#include <unordered_map>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 封装链表构建：根据存储的节点数据构建链表（注意：节点的输入顺序可能无序）
ListNode* buildLinkedList(unordered_map<int, pair<int, int>> &nodes, int head_addr) {
    unordered_map<int, ListNode*> addressMap; // 用于保存已创建的节点
    // 创建头节点
    ListNode *head = new ListNode(nodes[head_addr].first);
    addressMap[head_addr] = head;
    
    int curr_addr = nodes[head_addr].second;
    ListNode *prev = head;
    while (curr_addr != -1) {
        // 如果当前地址已创建，说明环出现，直接链接即可
        if (addressMap.find(curr_addr) != addressMap.end()) {
            prev->next = addressMap[curr_addr];
            break;
        }
        // 创建新节点
        ListNode *newNode = new ListNode(nodes[curr_addr].first);
        addressMap[curr_addr] = newNode;
        prev->next = newNode;
        prev = newNode;
        curr_addr = nodes[curr_addr].second;
    }
    return head;
}

// 使用快慢指针判断链表是否有环
bool hasCycle(ListNode *head) {
    if (!head || !head->next) return false;
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

int main(){
    int n;
    cin >> n;
    if(n == 0){
        cout << "false" << endl;
        return 0;
    }
    
    // 用于存储节点数据： {addr : (val, next_addr)}
    unordered_map<int, pair<int, int>> nodes;
    int head_addr, val, next_addr;
    // 读取第一行（头节点）
    cin >> head_addr >> val >> next_addr;
    nodes[head_addr] = {val, next_addr};
    // 读取剩余 n-1 行
    for (int i = 1; i < n; i++){
        int addr;
        cin >> addr >> val >> next_addr;
        nodes[addr] = {val, next_addr};
    }
    
    // 构建链表（按照 next_addr 链接）
    ListNode* head = buildLinkedList(nodes, head_addr);
    
    cout << (hasCycle(head) ? "true" : "false") << endl;
    return 0;
}

Python 版本

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 判断链表是否有环（快慢指针）
def has_cycle(head):
    if not head or not head.next:
        return False

    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

if __name__ == "__main__":
    n = int(input().strip())
    if n == 0:
        print("false")
        exit()

    nodes = {}
    head_addr, val, next_addr = map(int, input().split())
    nodes[head_addr] = (val, next_addr)

    for _ in range(n - 1):
        addr, val, next_addr = map(int, input().split())
        nodes[addr] = (val, next_addr)

    # 构建链表
    address_map = {}
    head = ListNode(nodes[head_addr][0])
    address_map[head_addr] = head

    curr_addr = nodes[head_addr][1]
    prev = head
    while curr_addr != -1:
        if curr_addr in address_map:  # 形成环
            prev.next = address_map[curr_addr]
            break

        new_node = ListNode(nodes[curr_addr][0])
        address_map[curr_addr] = new_node
        prev.next = new_node
        prev = new_node

        curr_addr = nodes[curr_addr][1]

    print("true" if has_cycle(head) else "false")

Java解法

import java.util.HashMap;
import java.util.Scanner;

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { 
        val = x; 
        next = null; 
    }
}

public class Main {
    
    // 构建链表：根据 nodes（addr -> [val, next_addr]）和头地址构建链表
    public static ListNode buildLinkedList(HashMap<Integer, int[]> nodes, int headAddr) {
        HashMap<Integer, ListNode> addressMap = new HashMap<>();
        ListNode head = new ListNode(nodes.get(headAddr)[0]);
        addressMap.put(headAddr, head);
        
        int currAddr = nodes.get(headAddr)[1];
        ListNode prev = head;
        while (currAddr != -1) {
            if (addressMap.containsKey(currAddr)) {  // 已创建，说明形成环
                prev.next = addressMap.get(currAddr);
                break;
            }
            ListNode newNode = new ListNode(nodes.get(currAddr)[0]);
            addressMap.put(currAddr, newNode);
            prev.next = newNode;
            prev = newNode;
            currAddr = nodes.get(currAddr)[1];
        }
        return head;
    }
    
    // 使用快慢指针判断链表是否存在环
    public static boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        if(n == 0){
            System.out.println("false");
            scanner.close();
            return;
        }
        
        // 存储节点数据： key 为 addr，value 为 int[]{val, next_addr}
        HashMap<Integer, int[]> nodes = new HashMap<>();
        
        // 读取头节点（第一行的三个整数）
        int headAddr = scanner.nextInt();
        int val = scanner.nextInt();
        int nextAddr = scanner.nextInt();
        nodes.put(headAddr, new int[]{val, nextAddr});
        
        for (int i = 1; i < n; i++) {
            int addr = scanner.nextInt();
            val = scanner.nextInt();
            nextAddr = scanner.nextInt();
            nodes.put(addr, new int[]{val, nextAddr});
        }
        
        ListNode head = buildLinkedList(nodes, headAddr);
        System.out.println(hasCycle(head) ? "true" : "false");
        scanner.close();
    }
}

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。