题目描述
给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。
思路
第一步,用两个快慢指针找环中相汇点。分别用slow
, fast
指向链表头部,slow
每次走一步,fast
每次走二步,直到fast == slow
找到在环中的相汇点。
第二步,找环的入口。当fast == slow
时,假设slow
走过x个节点,则fast
走过2x个节点。设环中有n个节点,因为fast
比slow
多走一圈(n个节点),所以有等式2x = n + x
,可以推出n = x
,即slow
实际上走了一个环的步数。这时,我们让fast
重新指向链表头部pHead
,slow
的位置不变,然后slow
和fast
一起向前每次走一步,直到fast == slow
,此时两个指针相遇的节点就是环的入口。
# -*- 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 is None:
return None
if pHead.next is None:
return None
p = pHead
q = pHead.next
while p!=q:
if q.next is not None and q.next.next is not None:
p = p.next
q = q.next.next
else:
break
if p ==q:
r = pHead
p = p.next
while r != p:
r = r.next
p = p.next
return r
else:
return None