141. 环形链表

约 4572 字大约 15 分钟

链表双指针哈希表

2025-05-13

原题

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。否则，返回 false 。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

链表中节点的数目范围是 [0, 10^4]
-10^5 <= Node.val <= 10^5
pos 为 -1 或者链表中的一个 有效索引 。

**进阶：**你能用 O(1)（即，常量）内存解决此问题吗？

在计算机科学中，链表是一种基础且常用的数据结构，而环形链表检测则是链表操作中的经典问题。在实际开发中，我们常常需要处理各种链式结构，如内存管理、图算法实现、缓存系统等。

审题

在面试中，面对这道环形链表检测问题，我们应该先向面试官提问，明确题目要求和边界情况。以下是一些关键问题：

候选人： "这道题目是判断一个链表是否有环，我想确认一下输入和输出的具体要求。"

面试官： "输入是链表的头节点，如果链表中存在环，返回true；否则返回false。"

候选人： "关于pos参数，我注意到题目中提到它只是用来表示链表的实际情况，不会作为函数参数传入，对吗？"

面试官： "是的，pos只是用来描述测试用例中环的位置，在实际代码中不会作为参数传入。你只会得到链表的头节点。"

候选人： "对于边界情况，如果输入是空链表（head为null），应该返回什么？"

面试官： "空链表没有环，应该返回false。"

候选人： "如果链表只有一个节点，且这个节点的next指向自身，这算是有环吗？"

面试官： "是的，这种情况下链表有环，应该返回true。"

候选人： "关于性能要求，题目提到进阶要求是使用O(1)空间复杂度，这是必须的吗？"

面试官： "不是必须的，但如果你能提供O(1)空间复杂度的解法会更好。先给出一个正确的解法，然后我们可以讨论如何优化。"

通过以上交流，我们明确了：

输入：链表的头节点head
输出：布尔值，表示链表是否有环
边界情况：
- 空链表返回false
- 单节点自环返回true
- pos不作为参数传入
性能要求：优先保证正确性，然后考虑使用O(1)空间复杂度的解法

解析

思路概述

环形链表检测是一个经典的算法问题，主要有两种常见解法：哈希表法和快慢指针法（Floyd 判圈算法）。

哈希表法的思路很直观：我们遍历链表，将每个节点存入哈希表，如果遇到已经在哈希表中的节点，说明链表有环；如果遍历结束都没有重复节点，说明链表无环。这种方法时间复杂度为O(n)，空间复杂度也为O(n)。

快慢指针法则更为巧妙，也是本题的最优解法。我们使用两个指针，一个慢指针每次移动一步，一个快指针每次移动两步。如果链表中存在环，两个指针最终会在环中相遇；如果链表没有环，快指针会先到达链表尾部。这种方法的时间复杂度为O(n)，而空间复杂度仅为O(1)，完美满足题目的进阶要求。

在实际开发中，我们常常会选择快慢指针法来检测链表是否有环，因为它不仅效率高，而且不需要额外的存储空间。

算法步骤

快慢指针法的具体步骤如下：

初始化两个指针slow和fast，均指向链表头节点head
进入循环，slow每次向前移动一步（slow = slow.next），fast每次向前移动两步（fast = fast.next.next）
如果链表中不存在环，fast指针会先到达链表尾部，此时返回false
如果链表中存在环，slow和fast指针会在环中的某个节点相遇，此时返回true
特殊情况处理：如果链表为空或只有一个节点且无环，直接返回false

这个算法的正确性基于一个数学事实：如果链表中存在环，快指针和慢指针一定会在环中相遇。这是因为每当慢指针移动一步，快指针就会移动两步，两者的距离每次都会缩小1，最终一定会相遇。

在代码实现时，我们需要注意几个关键点：

在移动fast指针前，需要检查fast及fast.next是否为null，避免空指针异常
循环终止条件是fast或fast.next为null（表示链表无环）或slow与fast相遇（表示链表有环）
对于空链表，应直接返回false

源码

核心代码模式

Java

/**
 * 环形链表检测 - 快慢指针法
 * 时间复杂度: O(n)，其中n是链表的节点数
 * 空间复杂度: O(1)，只使用了两个指针
 */
public 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;
    }
}

Python

# 环形链表检测 - 快慢指针法
# 时间复杂度: O(n)，其中n是链表的节点数
# 空间复杂度: O(1)，只使用了两个指针
class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        # 如果链表为空或只有一个节点，则不可能有环
        if not head or not head.next:
            return False
        
        # 初始化快慢指针
        slow = head
        fast = head
        
        # 快指针每次移动两步，慢指针每次移动一步
        # 如果链表有环，两个指针最终会相遇
        while fast and fast.next:
            slow = slow.next       # 慢指针移动一步
            fast = fast.next.next  # 快指针移动两步
            
            # 如果两个指针相遇，说明链表有环
            if slow == fast:
                return True
        
        # 如果快指针到达链表尾部，说明链表无环
        return False

JavaScript

/**
 * 环形链表检测 - 快慢指针法
 * 时间复杂度: O(n)，其中n是链表的节点数
 * 空间复杂度: O(1)，只使用了两个指针
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    // 如果链表为空或只有一个节点，则不可能有环
    if (!head || !head.next) {
        return false;
    }
    
    // 初始化快慢指针
    let slow = head;
    let fast = head;
    
    // 快指针每次移动两步，慢指针每次移动一步
    // 如果链表有环，两个指针最终会相遇
    while (fast && fast.next) {
        slow = slow.next;      // 慢指针移动一步
        fast = fast.next.next; // 快指针移动两步
        
        // 如果两个指针相遇，说明链表有环
        if (slow === fast) {
            return true;
        }
    }
    
    // 如果快指针到达链表尾部，说明链表无环
    return false;
};

/**
 * 环形链表检测 - 快慢指针法
 * 时间复杂度: O(n)，其中n是链表的节点数
 * 空间复杂度: O(1)，只使用了两个指针
 */
func hasCycle(head *ListNode) bool {
    // 如果链表为空或只有一个节点，则不可能有环
    if head == nil || head.Next == nil {
        return false
    }
    
    // 初始化快慢指针
    slow := head
    fast := head
    
    // 快指针每次移动两步，慢指针每次移动一步
    // 如果链表有环，两个指针最终会相遇
    for fast != nil && fast.Next != nil {
        slow = slow.Next       // 慢指针移动一步
        fast = fast.Next.Next  // 快指针移动两步
        
        // 如果两个指针相遇，说明链表有环
        if slow == fast {
            return true
        }
    }
    
    // 如果快指针到达链表尾部，说明链表无环
    return false
}

ACM模式

Java

import java.util.*;

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

public class Main {
    // 环形链表检测函数
    public static 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;
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        String[] input = scanner.nextLine().replace("[", "").replace("]", "").split(",");
        int pos = Integer.parseInt(scanner.nextLine());
        
        // 构建链表
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        ListNode cycleNode = null;
        
        for (int i = 0; i < input.length; i++) {
            current.next = new ListNode(Integer.parseInt(input[i]));
            current = current.next;
            
            // 记录环的入口节点
            if (i == pos) {
                cycleNode = current;
            }
        }
        
        // 如果pos有效，创建环
        if (pos >= 0 && cycleNode != null) {
            current.next = cycleNode;
        }
        
        // 检测环并输出结果
        boolean result = hasCycle(dummy.next);
        System.out.println(result);
        
        scanner.close();
    }
}

Python

# 链表节点定义
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def hasCycle(head):
    if not head or not head.next:
        return False
    
    slow = head
    fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            return True
    
    return False

# 读取输入
import sys

def main():
    # 读取输入
    input_str = input().strip().replace('[', '').replace(']', '')
    if input_str:
        values = list(map(int, input_str.split(',')))
    else:
        values = []
    pos = int(input().strip())
    
    # 构建链表
    dummy = ListNode(0)
    current = dummy
    cycle_node = None
    
    for i, val in enumerate(values):
        current.next = ListNode(val)
        current = current.next
        
        # 记录环的入口节点
        if i == pos:
            cycle_node = current
    
    # 如果pos有效，创建环
    if pos >= 0 and cycle_node:
        current.next = cycle_node
    
    # 检测环并输出结果
    result = hasCycle(dummy.next)
    print(str(result).lower())

if __name__ == "__main__":
    main()

JavaScript

// 链表节点定义
function ListNode(val) {
    this.val = val;
    this.next = null;
}

/**
 * 环形链表检测函数
 * @param {ListNode} head
 * @return {boolean}
 */
function hasCycle(head) {
    if (!head || !head.next) {
        return false;
    }
    
    let slow = head;
    let fast = head;
    
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        
        if (slow === fast) {
            return true;
        }
    }
    
    return false;
}

// 处理输入和输出
const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let lines = [];
rl.on('line', (line) => {
    lines.push(line);
    if (lines.length === 2) {
        // 解析输入
        const values = lines[0].replace('[', '').replace(']', '').split(',').map(x => parseInt(x.trim()));
        const pos = parseInt(lines[1]);
        
        // 构建链表
        const dummy = new ListNode(0);
        let current = dummy;
        let cycleNode = null;
        
        for (let i = 0; i < values.length; i++) {
            current.next = new ListNode(values[i]);
            current = current.next;
            
            // 记录环的入口节点
            if (i === pos) {
                cycleNode = current;
            }
        }
        
        // 如果pos有效，创建环
        if (pos >= 0 && cycleNode) {
            current.next = cycleNode;
        }
        
        // 检测环并输出结果
        const result = hasCycle(dummy.next);
        console.log(result);
        
        rl.close();
    }
});

package main

import (
    "fmt"
    "strings"
    "strconv"
)

// 链表节点定义
type ListNode struct {
    Val int
    Next *ListNode
}

// 环形链表检测函数
func hasCycle(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return false
    }
    
    slow := head
    fast := head
    
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        
        if slow == fast {
            return true
        }
    }
    
    return false
}

func main() {
    // 读取输入
    var input string
    fmt.Scanln(&input)
    input = strings.ReplaceAll(input, "[", "")
    input = strings.ReplaceAll(input, "]", "")
    
    var pos int
    fmt.Scanln(&pos)
    
    // 解析输入值
    var values []int
    if input != "" {
        valStrs := strings.Split(input, ",")
        values = make([]int, len(valStrs))
        for i, s := range valStrs {
            values[i], _ = strconv.Atoi(strings.TrimSpace(s))
        }
    }
    
    // 构建链表
    dummy := &ListNode{0, nil}
    current := dummy
    var cycleNode *ListNode
    
    for i, val := range values {
        current.Next = &ListNode{val, nil}
        current = current.Next
        
        // 记录环的入口节点
        if i == pos {
            cycleNode = current
        }
    }
    
    // 如果pos有效，创建环
    if pos >= 0 && cycleNode != nil {
        current.Next = cycleNode
    }
    
    // 检测环并输出结果
    result := hasCycle(dummy.Next)
    fmt.Println(result)
}

吊打面试官

在面试中，面试官往往不会仅仅满足于你能够解出题目，还会进一步追问一些问题来考察你的算法思维和技术深度。以下是面试官可能会问到的问题及其解答：

问题1：该算法的时间复杂度和空间复杂度是多少？如何计算的？

回答：

对于快慢指针法：

时间复杂度：O(n)，其中n是链表的节点数。
- 分析：如果链表中不存在环，快指针会先到达链表尾部，整个过程最多遍历一次链表，时间复杂度为O(n)。
- 如果链表中存在环，假设环的长度为k，非环部分长度为m，则在最坏情况下，慢指针需要走m步到达环的入口，然后再走k步才能与快指针相遇，总共走了m+k步，不超过链表总长度n，因此时间复杂度仍为O(n)。
空间复杂度：O(1)。
- 分析：我们只使用了两个指针（slow和fast），无论链表多长，所需的额外空间都是常量级的。

相比之下，哈希表法的空间复杂度为O(n)，因为需要存储访问过的所有节点。

问题2：为什么快慢指针一定会在环中相遇？能否证明这一点？

回答：

这是一个很好的问题。我们可以通过数学方式来证明快慢指针在环中一定会相遇：

假设慢指针进入环时，快指针已经在环中某个位置。此时，两个指针在环中的距离最多为环的长度k。

每经过一次迭代，慢指针移动1步，快指针移动2步，两者的距离会减少1（因为快指针比慢指针多走1步）。

因此，在最多k次迭代后，两个指针一定会相遇。这就证明了如果链表中存在环，快慢指针一定会在环中相遇。

从另一个角度看，可以将这个问题想象成"追及问题"：如果两个人在环形跑道上跑步，一个人速度是另一个人的两倍，那么快的人一定会在某个时刻从后面追上慢的人。

问题3：如果要求不仅检测环的存在，还要找出环的入口节点，如何修改算法？

回答：

这是LeetCode上的另一道题目（142. 环形链表 II）。我们可以在检测到环后，利用快慢指针的相遇点来找出环的入口：

首先使用快慢指针法检测环是否存在，如果存在，记录相遇点meet
将其中一个指针重新指向链表头节点head，另一个指针保持在相遇点meet
然后两个指针都以相同的速度（每次移动一步）向前移动
当两个指针再次相遇时，相遇点就是环的入口节点

这个算法的正确性基于以下数学关系：

设链表头到环入口的距离为a，环入口到相遇点的距离为b，相遇点到环入口的距离为c（注意b+c等于环的长度）
当快慢指针相遇时，慢指针走了a+b步，快指针走了a+b+n(b+c)步（n是快指针在环中额外走的圈数）
由于快指针的速度是慢指针的两倍，所以有：2(a+b) = a+b+n(b+c)
化简得：a = c+(n-1)(b+c)
这意味着从链表头走a步和从相遇点走c+(n-1)(b+c)步都会到达环的入口
由于c+(n-1)(b+c)表示从相遇点出发，走c步到达环入口，再绕环走(n-1)圈
因此，如果一个指针从链表头出发，另一个从相遇点出发，两者都以相同速度前进，它们会在环入口处相遇

这个扩展算法的时间复杂度仍为O(n)，空间复杂度为O(1)。

结语

环形链表检测是算法面试中的经典问题，通过本题的学习，我们不仅掌握了一种优雅的算法解法，更深入理解了指针操作和算法设计的精妙之处。

快慢指针法（Floyd 判圈算法）展示了如何在不使用额外空间的情况下解决看似复杂的问题。这种思路在许多其他算法问题中也有应用，如寻找数组中的重复元素、判断回文链表等。它告诉我们，有时候最优解并不是最直观的方法，而是需要我们转换思路，从问题的本质出发。

在实际开发中，我们常常需要处理各种链式结构和循环引用问题。环形链表检测的思想可以应用于内存泄漏检测、死锁预防、循环依赖分析等多个领域。掌握这一算法不仅有助于我们通过技术面试，更能帮助我们在日常工作中设计出更高效、更可靠的系统。

此外，这道题目也是理解时间复杂度和空间复杂度权衡的绝佳案例。哈希表法虽然直观，但需要O(n)的额外空间；而快慢指针法虽然思路不那么直接，却能将空间复杂度优化至O(1)。这提醒我们在算法设计中要全面考虑各种约束条件，根据实际场景选择最合适的解决方案。

最后，环形链表检测问题还向我们展示了数学思维在算法设计中的重要性。通过简单的数学关系，我们不仅能够证明算法的正确性，还能进一步扩展算法功能，如找出环的入口节点。这种数学思维对于解决更复杂的算法问题至关重要。

希望通过本文的讲解，你能够对环形链表检测问题有更深入的理解，并将这种思维方式应用到其他算法问题的解决中。记住，优秀的算法不仅能够解决问题，更能够以最优雅、最高效的方式解决问题。