141. 环形链表

使用 Set 使用

思路：使用 Set 记录访问过的节点

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
function hasCycle(head: ListNode | null): boolean {
  const set = new Set<ListNode>()
  let current: ListNode | null = head
  while(current !== null) {
    if (set.has(current)) {
      return true
    }
    set.add(current)
    current = current.next
  }
  return false
};

复杂度分析：

• 时间复杂度：
• 空间复杂度：

快慢指针

这里有一篇解释为什么快慢指针会在环内相遇，写得挺不错的：相爱相杀好基友——数组与链表。了解了为什么在环内相遇，就大致能理解如何使用快慢指针来进行求解：

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
function hasCycle(head: ListNode | null): boolean {
    // 如果 head 则表示链表中没有元素，如何 head.next 则表示当链表只有一个元素的时候，next 并没有指向自己
    if (head === null || head.next === null) {
        return false
    }
    // 定义快慢指针，慢指针步长为1，而快指针步长为2
    let slow = head
    let fast = head.next
    while(slow !== fast) {
        // 当快指针为 null 的时候，或者快指针的 next 指向 null 的时候，表明链表没有环
        if (fast === null || fast.next === null) {
            return false
        }
        // 慢指针的步长为 1
        slow = slow.next
        // 快指针的步长为 2
        fast = fast.next.next
    }
    return true
};