题目 1

题目链接

题目原文 给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪next指针再次到达，则链表中存在环。
为了表示给定链表中的环，我们使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。
如果pos是 −1-1，则在该链表中没有环。
注意：pos不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回true。否则，返回false。
进阶：

你能用 O(1)（即，常量）内存解决此问题吗？

示例示例

题目解析

该题仅需要判断链表中是否存在环，如果存在则返回True。很容易可以想到利用哈希表来存储已经遍历过节点的父节点，若发现某个节点存在两个父节点，则一定存在环。此外，我们可以利用双指针法来避免引入额外空间。

解题方法

哈希表

对于python我们可以将已经遍历过的节点放入set中，如果遍历过即返回True。

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        # 已访问过的节点集合
        visited = set([])
        ptr = head
        while ptr is not None:
            if ptr in visited:
                return True
            visited.add(ptr)
            ptr=ptr.next
        return False

复杂度分析：
时间复杂度：O(N)O(N)
空间复杂度：O(N)O(N)
可见该方法的空间复杂度较高，利用双指针方法可以不增加哈希表的额外空间。

双指针-快慢指针

该方法的思想很简单，设置一个快指针，一次走两步，一个慢指针，一次只走一步。若存在环，由于快指针比慢指针快，所以一定会追上慢指针。

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        # 快慢指针
        fast = head
        slow = head
        while fast is not None:
            slow = slow.next
            fast = fast.next
            if fast is None:
                return False
            fast = fast.next
            if slow == fast:
                # 两指针相遇，存在环
                return True

复杂度分析：
时间复杂度：O(N)O(N)。
空间复杂度：O(1)O(1)。只是用了两个指针的额外空间。

双指针-修改链表

换个角度，在允许修改链表的情况下，我们可以对链表进行修改，进而也可以不需要额外空间，判断链表是否存在环。
思路如下：
在遍历链表的同时，修改每个节点的值，或者修改链表结构，使得每个节点的next指针指向自身，构建一个小环。
此外，使用两个速度相同的指针，在遍历过程中修改链表。当遇到某个节点的next指向自身时，则发现环。

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        # 双指针
        first_point = head
        second_point = head
        # 每个节点遍历后指向自身
        while True:
            if first_point is None:
                return False
            if first_point == first_point.next:
                # 找到环 
                return True
            first_point = first_point.next
            second_point.next = second_point
            second_point = first_point

题目2

题目链接

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

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

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

题目解析

需要注意的是，本题不允许修改链表，并且需要给出开始入环的第一个节点。对于哈希表方法来说，修改十分简单，但是对于快慢指针，需要分析快慢指针的关系，进而计算快慢指针相遇时与入环点的距离。

解题方法

哈希表

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        # 已访问过的节点集合
        visited = set([])
        ptr = head
        while ptr is not None:
            if ptr in visited:
                return ptr
            visited.add(ptr)
            ptr=ptr.next
        return None

复杂度分析：
时间复杂度：O(N)O(N)。N为节点数。
空间复杂度：O(N)O(N)。最坏情况下遍历所有节点才能找到环。

双指针-快慢指针

首先，我们将有环链表分成3部分，如下图的a，b，c:

有环链表简化图有环链表简化图

假设，慢指针在走到图中紫色点时，快指针已经走了环的n圈，那么快指针所走的距离为：
a+n(b+c)+b=a+(n+1)b+c a+n(b+c)+b = a + (n+1)b + c
由快慢指针的速度可知，快指针是慢指针速度的二倍，走的距离也是慢指针的二倍，所以得到如下关系：
a+(n+1)b+c=2(a+b)a=(n−1)b+c a + (n+1)b + c = 2(a+b) \\ a = (n-1)b + c
由上式可知，从头结点到入环点的距离，正好等于从相遇点到入环点的距离加上n-1圈的环长。
因此，当快慢指针相遇时，我们可以再用一个额外指针，从头指针开始向后遍历，慢指针同时向后遍历，他们最终会在入环点相遇。

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        # 快慢指针
        fast = head
        slow = head
        ptr = None
        while fast is not None:
            slow = slow.next
            fast = fast.next
            if fast is None:
                return None
            fast = fast.next
            if slow == fast:
                # 快慢指针相遇
                ptr = head
                while slow != ptr:
                    slow = slow.next
                    ptr = ptr.next
                break
        return ptr

参考

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