142. 环形链表 II

题目

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

说明：不允许修改给定的链表。
进阶：**你是否可以使用 O(1) 空间解决此题？

实现

思路1 Hashset

首先该题与Leetcode第141题“环形链表”非常相似，很明显该题也能像第141题一样使用哈希表记录访问过的节点，直到找到已存在哈希表中的节点，那么该节点就是入环点。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_set<ListNode *> visited;
        while (head != nullptr) {
            if (visited.count(head)) {
                return head;
            }
            visited.insert(head);
            head = head->next;
        }
        return nullptr;
    }
};

思路2 双指针

该思路是查看官方题解才想到的方法，非常巧妙。
总结来说，也是使用了第141题“环形链表”的快慢指针方法，不过我们可以发现最终快慢指针相遇的地点与链表长度有一定的数学关系。即假设两指针相遇时快指针已绕环走了n圈，那么从相遇点到入环点的距离加上n-1圈的环长，恰好等于链表头部到入环点的距离。
推导方法就是根据快指针走的距离是满指针的两倍这条关系，列出一个距离的等式。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        # 因为关系是根据快指针走的距离是慢指针两倍推导的
        # 所以起始得设为一样的，否则距离关系也不一样
        slowPtr = head
        fastPtr = head
        while fastPtr:
            if not fastPtr.next:
                return None
            # 慢指针前进1步，快指针前进2步
            slowPtr = slowPtr.next
            fastPtr = fastPtr.next.next
            if fastPtr == slowPtr:
                tmp = head
                while tmp!= slowPtr:
                    tmp = tmp.next
                    slowPtr = slowPtr.next
                return tmp
        return None

时间复杂度：. 在一开始判断快慢指针是否相遇时，slow指针走国的距离不会超过链表总长度；随后寻找入环点时遍历的结点也不会超过链表总长度。
空间复杂度：.

参考**
https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode-solution/