题解 | 判断链表中是否有环

1、解题思路

快慢指针法（Floyd's Tortoise and Hare Algorithm）：

1. 使用两个指针，一个快指针（每次移动两步）和一个慢指针（每次移动一步）。
2. 如果链表有环，快指针最终会追上慢指针，两者会在环内相遇。
3. 如果链表无环，快指针会先到达链表末尾（null）。

这种方法满足空间复杂度 O(1)（只用了两个指针）和时间复杂度 O(n)（最多遍历链表两次）。

2、代码实现

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
  public:
    bool hasCycle(ListNode* head) {
        // 快慢指针初始化都指向头节点
        ListNode* slow = head;
        ListNode* fast = head;

        // 循环直到快指针或快指针的下一个节点为NULL
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;          // 慢指针每次移动一步
            fast = fast->next->next;    // 快指针每次移动两步

            // 如果快慢指针相遇，说明有环
            if (slow == fast) {
                return true;
            }
        }

        // 快指针到达链表末尾，说明无环
        return false;
    }
};

Java

import java.util.*;
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        // 快慢指针初始化都指向头节点
        ListNode slow = head;
        ListNode fast = head;

        // 循环直到快指针或快指针的下一个节点为NULL
        while (fast != null && fast.next != null) {
            slow = slow.next;          // 慢指针每次移动一步
            fast = fast.next.next;     // 快指针每次移动两步

            // 如果快慢指针相遇，说明有环
            if (slow == fast) {
                return true;
            }
        }

        // 快指针到达链表末尾，说明无环
        return false;
    }
}

Python

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

#
#
# @param head ListNode类
# @return bool布尔型
#
class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        # 快慢指针初始化都指向头节点
        slow = head
        fast = head

        # 循环直到快指针或快指针的下一个节点为None
        while fast and fast.next:
            slow = slow.next  # 慢指针每次移动一步
            fast = fast.next.next  # 快指针每次移动两步

            # 如果快慢指针相遇，说明有环
            if slow == fast:
                return True

        # 快指针到达链表末尾，说明无环
        return False

3、复杂度分析

• 时间复杂度：O(n)，其中 n 是链表的长度。最坏情况下，快指针遍历链表两次。
• 空间复杂度：O(1)，只使用了两个额外的指针。