142.环形链表II

链接：142.环形链表II
难度：Medium
标签：哈希表、链表、双指针
简介：给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

题解 1 - python

• 编辑时间：2023-07-30
• 执行用时：52ms
• 内存消耗：20.1MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        while fast and fast.next and fast.next != slow:
            slow = slow.next
            fast = fast.next.next
        if not fast or not fast.next:
            return None
        slow = head
        fast = fast.next.next
        while fast != slow:
            fast = fast.next
            slow = slow.next
        return slow

题解 2 - typescript

• 编辑时间：2020-10-10
• 执行用时：120ms
• 内存消耗：41.4MB
• 编程语言：typescript
• 解法介绍：利用 set 去重。

function detectCycle(head: ListNode | null): ListNode | null {
  if (head === null || head.next === null) return null;
  const set = new Set<ListNode>([head]);
  let temp = head;
  while (temp.next !== null) {
    if (set.has(temp.next)) return temp.next;
    set.add(temp.next);
    temp = temp.next;
  }
  return null;
}

题解 3 - cpp

• 编辑时间：2022-03-03
• 执行用时：8ms
• 内存消耗：7.3MB
• 编程语言：cpp
• 解法介绍：双指针， 快指针跑了 a+b+c+b 时，慢指针跑了 a+b。

class Solution {
   public:
    ListNode *detectCycle(ListNode *head) {
        if (!head) return NULL;
        ListNode *fast = head, *slow = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (fast == slow) break;
        }
        if (!(fast && fast->next)) return NULL;
        slow = head;
        while (slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }
};

题解 4 - typescript

• 编辑时间：2020-10-10
• 执行用时：100ms
• 内存消耗：40.9MB
• 编程语言：typescript
• 解法介绍：[参考链接](https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode-solution/)。

function detectCycle(head: ListNode | null): ListNode | null {
  if (head === null) return null;
  let f: ListNode | null = head;
  let s: ListNode | null = head;
  while (f !== null && f.next !== null) {
    f = f.next.next;
    s = s.next!;
    if (f === s) {
      let h: ListNode | null = head;
      while (h !== s) {
        h = h.next!;
        s = s.next!;
      }
      return h;
    }
  }
  return null;
}

题解 5 - typescript

• 编辑时间：2021-03-06
• 执行用时：104ms
• 内存消耗：40.8MB
• 编程语言：typescript
• 解法介绍：快慢指针。

function detectCycle(head: ListNode | null): ListNode | null {
  if (head === null || head.next === null) return null;
  let fast: ListNode | null = head;
  let slow: ListNode | null = head;
  while (fast !== null && fast.next !== null) {
    fast = fast!.next!.next;
    slow = slow!.next;
    if (fast === slow) break;
  }
  if (fast !== slow) return null;
  slow = head;
  while (fast !== slow) {
    fast = fast!.next;
    slow = slow!.next;
  }
  return slow;
}