141. 环形链表

题目描述

给定一个链表的头节点 head，判断链表中是否存在环。

• 链表中有环：链表的某个节点的 next 指针指向了链表中某个先前的节点，形成一个环。即从某个节点开始，你可以一直沿着 next 指针循环回到该节点。
• 链表中没有环：链表的每个节点的 next 指针指向 null，并且遍历完链表后会到达末尾。

你需要实现一个高效的算法，判断链表是否有环。

---

示例

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有环，尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有环，尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

---

解题思路

1. 快慢指针法（Floyd's Tortoise and Hare）

解决链表环形问题的常见高效方法是使用 快慢指针（Floyd's Cycle-Finding Algorithm）。该算法的思路是：

• 慢指针：每次移动一步。
• 快指针：每次移动两步。

为什么这种方法有效？

• 如果链表中存在环，快指针必定会比慢指针先进入环，而后它们必定会在环中相遇。
• 如果链表没有环，快指针会首先到达链表的末尾（即 null），此时我们可以确认链表没有环。

2. 为什么使用快慢指针？

• 空间复杂度：快慢指针法只需要常数的空间，因此其空间复杂度为 ( O(1) )。
• 时间复杂度：最多会遍历链表两次，第一次用快指针到达环的入口，第二次用快慢指针相遇，时间复杂度为 ( O(n) )。

---

代码实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取链表节点值
        String[] values = scanner.nextLine().split(" ");
        ListNode head = null;
        ListNode tail = null;
        for (String val : values) {
            if (!val.isEmpty()) {
                ListNode newNode = new ListNode(Integer.parseInt(val));
                if (head == null) {
                    head = newNode;
                    tail = newNode;
                } else {
                    tail.next = newNode;
                    tail = newNode;
                }
            }
        }

        // 读取环的位置（-1表示没有环）
        int pos = scanner.nextInt();

        // 如果需要创建环
        if (pos >= 0) {
            ListNode current = head;
            ListNode cycleNode = null;

            // 找到要形成环的节点
            for (int i = 0; current != null; i++) {
                if (i == pos) {
                    cycleNode = current;
                    break;
                }
                current = current.next;
            }

            // 将尾节点连接到指定节点
            if (cycleNode != null && tail != null) {
                tail.next = cycleNode;
            }
        }

        Solution solution = new Solution();
        boolean result = solution.hasCycle(head);

        System.out.println(result);

        scanner.close();
    }
}

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;  // 快指针到达链表末尾，说明没有环
    }
}

// 定义链表节点
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

---

代码详解

1. 初始化：

   • 创建两个指针：slow（慢指针）和 fast（快指针），都指向链表头节点。

2. 循环遍历：

   • 快指针每次移动两步，慢指针每次移动一步。
   • 如果快指针和慢指针相遇，则说明链表中有环，返回 true。
   • 如果快指针走到了链表的末尾（即 fast == null 或 fast.next == null），说明链表没有环，返回 false。

3. 边界条件：

   • 如果链表为空或者只有一个节点，则无法有环，直接返回 false。

4. 测试用例：

   • 测试了三种情况：
     • 有环：构造链表 3 -> 2 -> 0 -> -4 并形成环。
     • 有环：构造链表 1 -> 2 -> 1 并形成环。
     • 无环：构造链表 1。

---

时间复杂度和空间复杂度

• 时间复杂度：( O(n) )，其中 ( n ) 是链表的长度。在最坏的情况下，快指针需要遍历整个链表（一次到达末尾），慢指针在环中最多循环一圈。
• 空间复杂度：( O(1) )，只使用了常数空间来存储两个指针。

---