解题思路

本题要求在 不修改链表 的前提下，找到链表入环的第一个节点（如果有环），否则返回 null。

可以使用 快慢指针（Floyd 判圈算法） 来解决这个问题：

解法：快慢指针（Floyd 判圈算法）

1. 第一阶段：判断链表是否有环

   • 设定 慢指针 slow 和 快指针 fast，都从 head 出发：
     • slow 每次走一步 (slow = slow.next)。
     • fast 每次走两步 (fast = fast.next.next)。
   • 如果 fast 追上 slow，说明有环。
   • 如果 fast 或 fast.next 为空，说明无环，返回 null。

2. 第二阶段：找到入环的第一个节点

   • 让 slow 重新指向 head，fast 仍停留在相遇点。
   • 两个指针 每次都走一步 (slow = slow.next, fast = fast.next)。
   • 当 slow == fast 时，相遇点就是环的入口。

为什么这样做？

• 设 head 到 环入口 的距离为 a，环内相遇点到入口的距离为 c，环的长度为 b。
• 当 slow 和 fast 相遇时，fast 比 slow 多走了整环的整数倍：

  2(a + c) = a + c + k * b   (k 为整数)
  => a + c = k * b
  => a = k * b - c
  

• slow 重新回到 head，同时 fast 从相遇点开始，每次走一步：
  • slow 走 a 步到达入口
  • fast 也走 a 步到达入口
  • 两者相遇，入口就是入环点！

代码实现

Python

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

def detectCycle(head):
    """ 使用快慢指针找出链表环的起点 """
    slow, fast = head  # 初始化快慢指针

    # 第一阶段：判断是否有环
    while fast and fast.next:
        slow = slow.next  # 慢指针走一步
        fast = fast.next.next  # 快指针走两步
        if slow == fast:  # 相遇，说明有环
            break
    else:
        return None  # 没有环，返回 null

    # 第二阶段：找到环的入口
    slow = head  # 重新指向头部
    while slow != fast:  # 直到相遇
        slow = slow.next
        fast = fast.next

    return slow  # 返回入环点

if __name__ == "__main__":
    import sys
    input_data = sys.stdin.read().strip().split()
    if not input_data:
        sys.exit(0)
    n = int(input_data[0])
    if n == 0:
        print("null")
        sys.exit(0)
    values = list(map(int, input_data[1:n+1]))
    pos = int(input_data[n+1])
    
    # 手动构造链表
    nodes = [ListNode(val) for val in values]
    for i in range(n - 1):
        nodes[i].next = nodes[i+1]
    if pos != -1:
        nodes[-1].next = nodes[pos]
    head = nodes[0]
    
    # 调用函数查找环入口
    entry = detectCycle(head)
    if not entry:
        print("null")
    else:
        # 找到环入口对应的索引
        idx = 0
        node = head
        while node != entry:
            node = node.next
            idx += 1
        print(idx)

C++

#include <iostream>

using namespace std;

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

ListNode* detectCycle(ListNode *head) {
    ListNode *slow = head, *fast = head;

    // 第一阶段：判断是否有环
    while (fast && fast->next) {
        slow = slow->next;        // 慢指针走一步
        fast = fast->next->next;  // 快指针走两步
        if (slow == fast) break;  // 相遇，说明有环
    }
    
    if (!fast || !fast->next) return NULL; // 无环

    // 第二阶段：找到环的入口
    slow = head;  // 重新指向头部
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }

    return slow;  // 返回入环点
}

int main() {
    int n;
    cin >> n;
    if(n == 0) {
        cout << "null" << endl;
        return 0;
    }
    vector<int> vals(n);
    for (int i = 0; i < n; i++) {
        cin >> vals[i];
    }
    int pos;
    cin >> pos;
    
    // 构造链表
    vector<ListNode*> nodes;
    for (int i = 0; i < n; i++) {
        nodes.push_back(new ListNode(vals[i]));
    }
    for (int i = 0; i < n - 1; i++) {
        nodes[i]->next = nodes[i+1];
    }
    if (pos != -1) {
        nodes[n-1]->next = nodes[pos];
    }
    ListNode* head = nodes[0];
    
    // 查找环入口
    ListNode* entry = detectCycle(head);
    if (entry == nullptr) {
        cout << "null" << endl;
    } else {
        int idx = 0;
        ListNode* cur = head;
        while (cur != entry) {
            cur = cur->next;
            idx++;
        }
        cout << idx << endl;
    }
    return 0;
}

Java

import java.util.Scanner;

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

public class Main {
    public static ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;

        // 第一阶段：判断是否有环
        while (fast != null && fast.next != null) {
            slow = slow.next;       // 慢指针走一步
            fast = fast.next.next;  // 快指针走两步
            if (slow == fast) break; // 相遇，说明有环
        }

        if (fast == null || fast.next == null) return null; // 无环

        // 第二阶段：找到环的入口
        slow = head;  // 重新指向头部
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }

        return slow;  // 返回入环点
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        if(n == 0) {
            System.out.println("null");
            return;
        }
        
        // 读取链表节点的值
        int[] values = new int[n];
        for (int i = 0; i < n; i++) {
            values[i] = sc.nextInt();
        }
        // 读取 pos 值
        int pos = sc.nextInt();
        
        // 构造链表
        ListNode[] nodes = new ListNode[n];
        for (int i = 0; i < n; i++) {
            nodes[i] = new ListNode(values[i]);
        }
        for (int i = 0; i < n - 1; i++) {
            nodes[i].next = nodes[i+1];
        }
        if (pos != -1) {
            nodes[n - 1].next = nodes[pos];
        }
        
        ListNode head = nodes[0];
        ListNode entry = detectCycle(head);
        
        // 如果无环则输出 "null"，否则输出环入口的索引
        if (entry == null) {
            System.out.println("null");
        } else {
            int idx = 0;
            ListNode cur = head;
            while (cur != entry) {
                cur = cur.next;
                idx++;
            }
            System.out.println(idx);
        }
    }
}

题目描述

给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

如果链表中存在某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，输入数据中使用整数 pos 来表示链表尾部连接的索引（索引从 0 开始）。如果 pos 为 -1，则表示该链表中没有环。

注意：pos 不作为参数进行传递，仅用于描述链表的实际情况，输入数据仅提供链表的结构。

不允许修改链表。

输入描述

• 第一行输入一个整数 n（$0 \leq n \leq 10^4$），表示链表的节点数。
• 第二行输入 n 个整数，表示链表节点的值（按顺序存储）。
• 第三行输入一个整数 pos（$-1 \leq pos < n$），表示链表尾部连接的索引，-1 代表无环。

如果 n == 0，则链表为空，此时 pos 必定为 -1，且不输入第二行数据。

输出描述

• 如果链表有环，返回环的起始节点的索引（从 0 开始）。
• 如果链表无环，返回 "null"。

样例1

输入

4
3 2 0 -4
1

输出

1

说明

链表中有一个环，其尾部连接到索引 1 的节点（值 2）。

样例2

输入

2
1 2
0

输出

0

说明

链表中有一个环，其尾部连接到索引 0 的节点（值 1）。

样例3

输入

1
1
-1

输出

null

说明

链表中没有环。

提示

• 链表的节点值范围：$-10^5 \leq \text{Node.val} \leq 10^5$。
• pos 仅用于构造链表，实际链表中不包含 pos 信息。
• pos = -1 表示链表无环。