zhangdizhangdi

141.环形链表

题目

LeetCode 简单

题目

链表中环的入口节点对于一个给定的链表，返回环的入口节点，如果没有环，返回 null。

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

题解

方法：Set

Set O(n) O(n)

ts
function hasCycle(head: Node): boolean {
  const tempSet = new Set()
  while (head) {
    if (tempSet.has(head)) {
      return true
    }
    tempSet.add(head)
    head = head.next
  }
  return false
}

const list = new CircularLinkedList([3, 2, 0, -4], 1)
console.log('🌰', hasCycle(list.head))

方法：双指针

双指针 O(n) O(1)

ts
function hasCycle(head: Node): boolean {
  let slow = head
  let fast = head
  while (fast && fast.next) {
    //慢指针每次只移动一步，而快指针每次移动两步。
    slow = slow.next
    fast = fast.next.next

    console.log('slow', slow)
    console.log('fast', fast)

    if (slow === fast) {
      console.log('相遇：', fast)

      return true
    }
  }
  return false
}

const list = new CircularLinkedList([3, 2, 0, -4], 1)
console.log('🌰', hasCycle(list.head))