Leetcode 142. Linked List Cycle II

地址：Leetcode 142. linked list Cycle II

问题描述：检测链表是否存在环，是的话返回环入口，否则返回None.

这道题有两个思路，一个是经典的快慢指针的思路，另外一个是利用hashMap来记住已经访问过的Node。

思路一：检测到环的时候，令慢指针指向head，然后fast 和 slow指针皆一次移动一个，到他们再次相遇的时候就是环的入口。
简单证明如下，来自Leetcode网友：

代码：

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return None
        slow,fast = head,head
        while(fast and fast.next):
            slow = slow.next
            fast = fast.next.next
            if (slow == fast):
                slow = head
                while(slow!=fast):
                    slow = slow.next
                    fast = fast.next
                return slow  #返回入口节点
        return None

思路二：利用一个hashMap当再次访问节点的时候就是环的入口。

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        
        visited = {}
        p = head
        while(p):
            if visited.get(p) != None:
                return p
            else:
                visited[p] = True
            p = p.next
        return None

最后总结来自：will_duan博客

目前我遇到的主要有以下几点应用：

• 如上面第一题，判断一个链表是否有环
• 如上面第二题，求一个链表是否存在环，如果存在，则求出环的入口结点
• 另一个应用是求链表是否存在环的变式，如给定两个链表A和B，判断两个链表是否相交，解决方法就是将A链表尾节点指向头结点形成一个环，检测B链表是否存在环，如果存在，则两个链表相交，而检测出来的依赖环入口即为相交的第一个点。
• 求有序链表中求出其中位数，这种问题也是设置快慢指针，当快指针到底链表尾部的时候，慢指针刚好指向链表中间的结点。