Link to LeetCode Problem

S1: 哈希表

1. 从头开始遍历链表并给每个节点增加一个“已遍历”的标记。
2. 如果在遍历过程中遇到了一个“已遍历”的节点，说明这是环的入口。
3. 但题目不允许修改给定的链表节点，因此可以借用一个额外的哈希表来记录。
4. 注意题目中没有提到节点值是否唯一，仅用节点值作为哈希表的 key 是不够的，需要用节点引用。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        set<ListNode*> seen;
        ListNode *cur = head;
        while (cur != NULL) {
            if (seen.find(cur) != seen.end()) return cur;
            seen.insert(cur);
            cur = cur->next;
        }
        return NULL;
    }
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function (head) {
  const map = new Map();

  while (head) {
    if (map.has(head)) return head;
    map.set(head, true);
    head = head.next;
  }

  return null;
};

• Time: $O(N)$，N 为链表长度。
• Space: $O(N)$，哈希表的空间。

S2: 双指针

1. 先使用快慢指针来确定链表是否有环。
2. 如果链表有环，那快慢指针相遇的点一定是在环中：
   1. 接着把指针 A 移到链表头部，指针 B 留在环内；
   2. 指针 A 走一步，指针 B 在环内走一圈；
   3. 如果指针 A 和指针 B 相遇了，说明这个节点就是环的入口。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        slow = fast = head

        while slow != None and fast != None and fast.next != None:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return self.findConnection(head, slow)
        return None

    def findConnection(self, head, loopNode):
        p1 = head
        while True:
            p2 = loopNode
            while p2.next != loopNode and p2.next != p1:
                p2 = p2.next
            if p2.next == p1:
                return p1
            p1 = p1.next

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function (head) {
  let slow = head,
    fast = head;
  // 快慢指针确定有环
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    // 确定有环，开始找环的第一个节点
    if (slow === fast) return findConnection(head, fast);
  }
  return null;

  // ******************************************

  function findConnection(head, loopNode) {
    // p1 走一步，p2 绕环一圈
    let p1 = head;
    while (true) {
      let p2 = loopNode;
      while (p2.next !== loopNode && p2.next !== p1) {
        p2 = p2.next;
      }
      if (p2.next === p1) return p1;
      p1 = p1.next;
    }
  }
};

• Time: $O(N*P)$，N 是环外链表的长度，P 是环的长度。
• Space: $O(1)$

S3: 双指针+数学证明

先用快慢指针确定链表是否有环，如果是环形链表，快慢指针会在环内的某个节点相遇。