Skip to content

如何判断一个单向链表是否是循环链表?

Posted on:2024年9月3日 at 01:42

判断一个单向链表是否是循环链表,常用的两种方法是哈希表法快慢指针法(也称为Floyd 判圈算法)。这两种方法都能有效地检测链表是否有环,但它们的时间复杂度和空间复杂度不同。

1. 哈希表法

原理:使用一个哈希表来记录链表中每个节点的引用。如果在遍历过程中遇到一个已经在哈希表中的节点,则说明链表有环。

步骤

  1. 创建一个空的哈希表。
  2. 遍历链表的每个节点:
    • 如果当前节点已经存在于哈希表中,则链表有环。
    • 否则,将当前节点加入哈希表。
  3. 如果遍历完链表没有发现重复的节点,则链表无环。

代码示例(JavaScript):

function hasCycle(head) {
  const visited = new Set();
  let current = head;

  while (current) {
    if (visited.has(current)) {
      return true; // 链表有环
    }
    visited.add(current);
    current = current.next;
  }

  return false; // 链表无环
}

优点:简单直观。

缺点:需要额外的空间来存储哈希表,空间复杂度为 O(n)。

2. 快慢指针法(Floyd 判圈算法)

原理:使用两个指针,一个快指针(每次移动两个节点)和一个慢指针(每次移动一个节点)。如果链表有环,快指针和慢指针最终会在环内相遇。如果链表无环,快指针会先到达链表末尾(即 null)。

步骤

  1. 初始化快指针和慢指针,都指向链表头部。
  2. 移动快指针两步,慢指针一步。
  3. 如果快指针和慢指针相遇,则链表有环。
  4. 如果快指针到达链表末尾(即 null),则链表无环。

代码示例(JavaScript):

function hasCycle(head) {
  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(1)。

缺点:相对复杂一些,但更节省空间。

原文转自:https://fe.ecool.fun/topic/0d218a9a-7477-48b0-b592-2e1f501668e7