分析这个问题:
- 是否包含环:
(1) 检测是否包含环,可以用两个速度不一样的指针,一个每次走两步,一个每次走一步,如果快的与慢的相遇了,则一定是存在环,且相遇节点是环中的一个节点, 而如果其中有一个到达了链表的尾端,则一定不存在环,存在环的时候遍历无法到达尾部
(2) 如果存在环,则返回相遇的节点,不存在返回None
(3)思路:慢指针走一步,快指针走两步,当有一个指针到达尾端,即==None时,没有环返回None
代码:
def meetingNodes(pHead):
if pHead == None:
return None
pSlow = pHead.next
if pSlow == None:
return None
pFast = pSlow.next
while pSlow != None and pFast != None:
if pFast == pSlow:
return pSlow
pSlow = pSlow.next
pFast = pFast.next
if pFast != None:
pFast = pFast.next
return None
- 环的入口
上面的程序返回了环中的一个节点,根据这个节点,我们可以计算出环中共有多少个节点。
def computeLength(pNode):
cur = pNode
length = 1
pNode = pNode.next
while pNode != cur:
length += 1
pNode = pNode.next
return length
- 有了环的长度,设置两个指针(速度相同),让p1先行进n步,然后两个指针一起走,当两个指针再次相遇的时候,就是环的入口。
代码:
def findEntry(pHead):
pNode = meetingNodes(pHead)
if pNode == None:
return None
n = computeLength(pNode)
pNode1 = pHead
for i in range(n):
pNode1 = pNode1.next
pNode2 = pHead
while pNode1 != pNode2:
pNode1 = pNode1.next
pNode2 = pNode2.next
return pNode1
牛客AC代码:
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def EntryNodeOfLoop(self, pHead):
# write code here
pNode = self.meetingNodes(pHead)
if pNode == None:
return None
n = self.computeLength(pNode)
pNode1 = pHead
for i in range(n):
pNode1 = pNode1.next
pNode2 = pHead
while pNode1 != pNode2:
pNode1 = pNode1.next
pNode2 = pNode2.next
return pNode1
def meetingNodes(self, pHead):
if pHead == None:
return None
pSlow = pHead.next
if pSlow == None:
return None
pFast = pSlow.next
while pSlow != None and pFast != None:
if pFast == pSlow:
return pSlow
pSlow = pSlow.next
pFast = pFast.next
if pFast != None:
pFast = pFast.next
return None
def computeLength(self, pNode):
cur = pNode
length = 1
pNode = pNode.next
while pNode != cur:
length += 1
pNode = pNode.next
return length