题目描述

题目：环形链表

给定一个链表的头节点 head，判断链表中是否有环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

示例 1:

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

示例 2:

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

示例 3:

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

解题思路

为了检测链表中是否存在环，我们可以使用快慢指针（也称为Floyd的循环查找算法或龟兔赛跑算法）。在这个算法中，我们设置两个指针，一个快指针（每次移动两步）和一个慢指针（每次移动一步）。如果链表中存在环，那么快慢指针最终会在环内的某个位置相遇。如果链表中不存在环，那么快指针会先到达链表末尾。

PHP 示例代码

<?php

class ListNode {
    public $val;
    public $next;
    function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}

function hasCycle($head) {
    if ($head == null || $head->next == null) {
        return false;
    }
    
    $slow = $head;
    $fast = $head->next;
    
    while ($slow != $fast) {
        if ($fast == null || $fast->next == null) {
            return false;
        }
        $slow = $slow->next;
        $fast = $fast->next->next;
    }
    
    return true;
}

// 示例用法
$head = new ListNode(3);
$head->next = new ListNode(2);
$head->next->next = new ListNode(0);
$head->next->next->next = $head->next; // 创建一个环

if (hasCycle($head)) {
    echo "链表中存在环";
} else {
    echo "链表中不存在环";
}
?>

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.next
    
    while slow != fast:
        if not fast or not fast.next:
            return False
        slow = slow.next
        fast = fast.next.next
    
    return True

# 示例用法
head = ListNode(3)
head.next = ListNode(2)
head.next.next = ListNode(0)
head.next.next.next = head.next  # 创建一个环

if hasCycle(head):
    print("链表中存在环")
else:
    print("链表中不存在环")

JavaScript 示例代码

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

function hasCycle(head) {
    if (!head || !head.next) {
        return false;
    }
    
    let slow = head;
    let fast = head.next;
    
    while (slow !== fast) {
        if (!fast || !fast.next) {
            return false;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    
    return true;
}

// 示例用法
let head = new ListNode(3);
head.next = new ListNode(2);
head.next.next = new ListNode(0);
head.next.next.next = head.next; // 创建一个环

if (hasCycle(head)) {
    console.log("链表中存在环");
} else {
    console.log("链表中不存在环");
}

这些示例代码分别展示了如何在PHP、Python和JavaScript中检测链表中是否存在环。在面试中，理解这种类型的问题并能用至少一种语言实现是很重要的。