题目描述:给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出 null。
Solutions
其实这一个问题可以分解成三个子问题:
- 如何判断链表中是否包含环?
- 两个指针,一个走一步,一个走两步,如果有环俩指针必相遇。
- 如何确定环中节点的个数?
- 在 1 的基础上,从相遇点开始,一步一步走,边走边计数,回到当前结点时就走了一圈。
- 如何找到环的入口结点?
- 在 1 的基础上,假设慢的指针走了 $x$ 步,那么快的指针走了 $2x$ 步,而多走的部分都是在环上走的,下面细说。
基于上面的图,我们知道快指针慢指针多走了 x 步,多走的部分都是在环上走的,那么可以得到式子:
\[2x - x = x = p(b+c)\]慢指针走过的步数有可以表示为:
\[x=a + q(b+c) + b\]集合上面两个式子可得:
\[p(b+c) = a + q(b+c) + b\] \[a = (p-q)(b+c)-b = (p-q-1)(b+c)+c\]通过上面的式子我们知道,当从相遇点开始,我们重新找两个指针,一个在头节点位置,一个在相遇点,两个指针每次都走一步,这样的话肯定会在换入口处相遇。
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def EntryNodeOfLoop(self, pHead):
# write code here
pSlow = pHead.next
if pSlow is None:
return None
pFast = pHead.next.next
b_loop = False
while pSlow is not None and pFast is not None:
if pSlow == pFast:
b_loop = True
break
pSlow = pSlow.next
if pSlow is None:
return None
pFast = pFast.next.next
if not b_loop:
return None
pRestart = pHead
while True:
if pRestart == pSlow:
return pRestart
pRestart = pRestart.next
pSlow = pSlow.next
# 运行时间:32ms
# 占用内存:5844k