给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。
解题思路:
在链表判环的基础上进行优化
追击问题,一快一慢可以再环中相遇 p1=p1.next; p2=p2.next.next
那么如何找到环的入口
针对一快一慢的节点,慢节点走的路成为s,则快的为2s,当两节点在环中环绕n圈
2s = s + nc
对于慢节点 s = a + x
两式子结合
a + x = nc
a = nc - x
a = (n-1)c + c-x
a = kc + (c-x)
我们可以看出 c-x为从相遇点继续走回到环入口的距离,所以可以看出如果一个节点从表头出发,一个节点从两点相遇点出发(一次一步),必回相遇。
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def EntryNodeOfLoop(self, pHead):
# write code here
if pHead == None or pHead.next == None:
return None
p1 = pHead
p2 = pHead
while True:
if p1 == None or p2 == None:
return None
p1 = p1.next
p2 = p2.next.next
if p1 == p2:
break
if p1 == p2:
pp = pHead
while pp != p1:
pp = pp.next
p1 = p1.next
return pp
else:
return None
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)