跳到主要内容

环形题库

题一、判断链表中是否有环​

给定一个链表，判断链表中是否有环。

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

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

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

示例1:

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

示例2:

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

方案A、哈希表​

思路: 遍历所有节点，每次遍历到一个节点时，判断该节点此前是否被访问过。具体来讲,我们可以使用哈希表来存储所有已经访问过的节点。每次我们到达一个节点，如果该节点已经存在于哈希表中，则说明该链表是环形链表，否则就将该节点加入哈希表中。重复这一过程，直到我们遍历完整个链表即可。

实现

function hasCycle(head){
  const set = new Set();
  while(head != null){
    if(set.has(head)){
      return true;
    }
    set.add(head);
    head = head.next;
  }
  return false;
}

方案B、快慢指针​

思路: 使用快慢指针法， 分别定义 fast 和 slow 指针。从头结点出发,fast指针每次移动两个节点,slow指针每次移动一个节点。如果 fast 和 slow 指针在途中相遇 ，说明这个链表有环。

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

性能分析:

  • 时间复杂度：O(N)，其中 N 是链表中的节点数。

    • 当链表中不存在环时，快指针将先于慢指针到达链表尾部，链表中每个节点至多被访问两次。
    • 当链表中存在环时，每一轮移动后，快慢指针的距离将减小一。而初始距离为环的长度，因此至多移动 N 轮。

  • 空间复杂度：O(1)。我们只使用了两个指针的额外空间。

题二、链表中环的入口结点​

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明:不允许修改给定的链表。

进阶:你是否可以使用 O(1) 空间解决此题？

示例1:

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

示例2:

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

方案A、哈希表​

思路

遍历链表中的每个节点，并将它记录下来；一旦遇到了此前遍历过的节点，就可以判定链表中存在环。借助哈希表可以很方便地实现。

实现

function detectCycle(head){
  const set = new Set();
  while(head != null){
    if(set.has(head)){
      return head;
    } 
    set.add(head);
    head = head.next;
  }
  return null;
}

方案B、快慢指针​

思路

使用两个指针, fast 与 slow。它们起始都位于链表的头部。随后,slow 指针每次向后移动一个位置，而 fast 指针向后移动两个位置。如果链表中存在环，则 fast 指针最终将再次与 slow 指针在环中相遇。如下图所示，设链表中环外部分的长度为 a。slow 指针进入环后，又走了 b 的距离与 fast 相遇。此时，fast 指针已经走完了环的 n 圈，因此它走过的总距离为 a+n(b+c)+b=a+(n+1)b+nc。

Preview

根据题意，任意时刻，fast 指针走过的距离都为 slow 指针的 2 倍。因此，我们有 a+(n+1)b+nc=2(a+b)⟹a=c+(n−1)(b+c)。有了 a=c+(n-1)(b+c)a=c+(n−1)(b+c) 的等量关系，我们会发现: 从相遇点到入环点的距离加上 n−1 圈的环长，恰好等于从链表头部到入环点的距离。因此，当发现 slow 与 fast 相遇时，我们再额外使用一个指针 ptr。起始，它指向链表头部；随后，它和 slow 每次向后移动一个位置。最终，它们会在入环点相遇。

实现

function detectCycle(head){
  if(head == null){
    return null;
  }
  let slow = head;
  let fast = head;
  while(fast != null){
    slow = slow.next;
    if(fast.next != null){
      fast = fast.next.next;
    }else{
      return null;
    }
    if(fast === slow){
      let ptr = head;
      while(ptr !== slow){
        ptr = ptr.next;
        slow = slow.next;
      }
      return ptr;
    }
  }
  return null;
}