Leetcode 142. Linked List Cycle II
我的博客
地址：Leetcode 142. linked list Cycle II
问题描述：检测链表是否存在环，是的话返回环入口，否则返回None.
这道题有两个思路，一个是经典的快慢指针的思路，另外一个是利用hashMap来记住已经访问过的Node。
思路一：检测到环的时候，令慢指针指向head，然后fast 和 slow指针皆一次移动一个，到他们再次相遇的时候就是环的入口。
简单证明如下，来自Leetcode网友：
image
代码：
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链表是否存在环，如果存在，则两个链表相交，而检测出来的依赖环入口即为相交的第一个点。
- 求有序链表中求出其中位数，这种问题也是设置快慢指针，当快指针到底链表尾部的时候，慢指针刚好指向链表中间的结点。
