142. 环形链表 II(medium)

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 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
解释：链表中没有环。

• show the code:

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
### code1
class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        dic = {None}
        while head:
            if head not in dic:
                dic.add(head)
                head = head.next
            else:
                return head
### code2
class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return head
        slow,quick = head,head
        iscycle = False
        while quick.next and quick.next.next:
            slow = slow.next
            quick = quick.next.next
            if quick == slow:
                iscycle = True
                break
        if iscycle:
            pointer1 = head
            pointer2 = slow
            while pointer1 != pointer2:
                pointer1 = pointer1.next
                pointer2 = pointer2.next
            return pointer1
        else:
            return None

• 此题是上一题环形链表的进阶版
• 首先代码一是常规方法哈希法，返回第一个重复出现的节点即可。
• 代码二的方法则比较有难度，其是根据一个规律：快慢指针同时从头节点出发，若链表有环，则一定会相遇，记录下这个相遇的节点，重新放一个指针在此节点上，一个指针在头节点，两者每次向前移动一步，则他们俩一定会在环的入口相遇。
• 因此代码二分为两个步骤：第一步找出链表中快慢指针相遇的节点，同时也判断了链表中是否有环，这里与上一题不同的是快慢指针的起点是相同的。第二步则重新定位两个指针，一个在上一步得到的相遇点处，一个在头节点处，两指针保持一样的速度，他们相遇的节点则是我们的结果。

• 有关上面代码二算法证明在官方题解里有详细说明：

  
  

代码二的空间复杂度降到了