【LeetCode】141 环形链表 I，142. 环形链表 II（双指针中学追及问题）

一. 题目描述：

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

【示例 1】：
输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。

【示例 2】：
输入：head = [1,2], pos = 0
输出：tail connects to node index 0
解释：链表中有一个环，其尾部连接到第一个节点。

【示例 3】：
输入：head = [1], pos = -1
输出：no cycle
解释：链表中没有环。

【进阶】：
你是否可以不用额外空间解决此题？

二. 解题说明：

2.1. 判断是否有环（LeetCode No.141 环形链表 I ）

总体思路就是去判断链表中有没有重复的节点（这里指的重复并不只是节点的value值相等，而是整个节点包括指针也相同，如果只判断节点的值相同，那么会对值相同的节点误判）。

判断是否有重复节点有3种方法，暴力法,哈希表法和双指针法。暴力法一般是错的，时间复杂度O(n^2)

2.1.1 哈希表法

哈希表是用空间换时间，将历史遍历都的节点保存都哈希表，而后每遍历下一个节点，就去哈希表中用O(1)的时间去查找是否已经存在，存在则有环，不存在则无环。时间复杂度O(n)，空间复杂度O(n)。

class Solution(object):
    def hasCycle(self, head):                 
        s = set()             # 定义一个set，然后不断遍历链表
        while head:
                              # 如果某个节点在set中，说明遍历到重复元素了，也就是有环
            if head in s:     # 不能把head.val这个值存在哈希表中，因为有可能只是值相同还不够，还需要指针也相同
                return True
            s.add(head)       # 如果节点不在哈希表中，说明之前没有相同节点，就存入表中 
            head = head.next
        return False

2.1.2 双指针法

本题解法与 LeetCode 160 题类似：

【LeetCode 】160. 相交链表（双指针法 Python 7行代码）.

双指针法利用了追击问题原理，如果链表中存在圆环，那么快（runner）慢（walker）两人速度不同，从同一条直线进入环形跑道，那么迟早会相遇。如果没有环形跑道则不会相遇。时间复杂度O(n)，空间复杂度O(1)。

# 【快慢指针】【龟兔赛跑】【追击问题】 时间 O(n)，空间O(1)
class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if (head is None) or (head.next is None):
            return False
        walker = head      # 快慢两人起点相同
        runner = head
        while(runner and runner.next):   # 用快者当临界
            walker = walker.next         # 每次走一步
            runner = runner.next.next    # 每次走两步
            if walker == runner:         # 能相遇，即有环，同样这里不能用walker.val == runner.val,因为值可能重复，但是指针指向地址不可能重复
                return True
        return False

2.2. 寻找环的入口

寻找环的入口只能采用【双指针法】，即追击问题的解法。具体推导如下：

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:

        walker = head
        runner = head
        while(runner and runner.next):
            walker = walker.next
            runner = runner.next.next
            if walker == runner:
                break
        if (runner is None) or (runner.next is None):  # 如果是因为走到头而退出循环，那就是没有环
            return                                     # return False 的话会报错Your returned value is not a ListNode type.
        # 如果是因为break而跳出循环，那就是有环
        walker = head             # 步行者回到起点
        while(walker != runner):  # 没相遇
            walker = walker.next
            runner = runner.next
        return runner

3. 举一反三

本题与以下一题，均采用追及问题 + 双指针（快慢指针）解决问题。