地址: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博客
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。