給定一個(gè)鏈表，返回鏈表開(kāi)始入環(huán)的第一個(gè)節(jié)點(diǎn)。 如果鏈表無(wú)環(huán)，則返回 null。
為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來(lái)表示鏈表尾連接到鏈表中的位置（索引從 0 開(kāi)始）。 如果 pos 是 -1，則在該鏈表中沒(méi)有環(huán)。
說(shuō)明：不允許修改給定的鏈表。
示例 1：
輸入：head = [3,2,0,-4], pos = 1
輸出：tail connects to node index 1
解釋：鏈表中有一個(gè)環(huán)，其尾部連接到第二個(gè)節(jié)點(diǎn)。
示例 2：
輸入：head = [1,2], pos = 0
輸出：tail connects to node index 0
解釋：鏈表中有一個(gè)環(huán)，其尾部連接到第一個(gè)節(jié)點(diǎn)。
示例 3：
輸入：head = [1], pos = -1
輸出：no cycle
解釋：鏈表中沒(méi)有環(huán)。

• 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

• 此題是上一題環(huán)形鏈表的進(jìn)階版
• 首先代碼一是常規(guī)方法哈希法，返回第一個(gè)重復(fù)出現(xiàn)的節(jié)點(diǎn)即可。
• 代碼二的方法則比較有難度，其是根據(jù)一個(gè)規(guī)律：快慢指針同時(shí)從頭節(jié)點(diǎn)出發(fā)，若鏈表有環(huán)，則一定會(huì)相遇，記錄下這個(gè)相遇的節(jié)點(diǎn)，重新放一個(gè)指針在此節(jié)點(diǎn)上，一個(gè)指針在頭節(jié)點(diǎn)，兩者每次向前移動(dòng)一步，則他們倆一定會(huì)在環(huán)的入口相遇。
• 因此代碼二分為兩個(gè)步驟：第一步找出鏈表中快慢指針相遇的節(jié)點(diǎn)，同時(shí)也判斷了鏈表中是否有環(huán)，這里與上一題不同的是快慢指針的起點(diǎn)是相同的。第二步則重新定位兩個(gè)指針，一個(gè)在上一步得到的相遇點(diǎn)處，一個(gè)在頭節(jié)點(diǎn)處，兩指針保持一樣的速度，他們相遇的節(jié)點(diǎn)則是我們的結(jié)果。

• 有關(guān)上面代碼二算法證明在官方題解里有詳細(xì)說(shuō)明：

  
  

代碼二的空間復(fù)雜度降到了