Skip to main content

141.环形链表

标签: linked-list, two-pointers

难度: Easy

通过率: 51.55%

原题链接: https://leetcode.com/problems/linked-list-cycle/description/

题目描述

给定一个链表的头结点,判断链表中是否存在环。存在环是指某个节点可以通过连续跟随 next 指针再次到达。返回 true 如果链表中存在环,否则返回 false

解题思路

判断链表是否有环的经典方法是使用快慢指针(Floyd's Cycle-Finding Algorithm)。我们设置两个指针,一个快指针 fast 每次移动两个节点,一个慢指针 slow 每次移动一个节点。初始时,两者都指向链表的头节点。如果链表中存在环,快指针最终会追上慢指针,否则快指针会到达链表的末尾。

具体步骤如下:

  1. 初始化两个指针 slowfast,都指向链表的头节点。
  2. 进入一个循环,直到 fastfast.nextnull
    • slow 指针前进一步。
    • fast 指针前进两步。
    • 如果在任何时刻 slowfast 相遇,则链表有环。
  3. 如果循环结束且没有相遇,返回 false,表示链表无环。

代码实现

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

def hasCycle(head):
if not head or not head.next:
return False
slow, fast = head, head.next
# 使用快慢指针来检测环
while fast and fast.next:
if slow == fast:
return True
slow = slow.next
fast = fast.next.next
return False

复杂度分析

时间复杂度:O(n)O(n),其中 nn 是链表中结点的数量。在循环中快指针和慢指针最多运行 nn 步。
空间复杂度:O(1)O(1),我们只使用了两个指针。