塞进裤子ヾ(≧O≦)〃嗷~

0%

剑指offer-23链表中环的入口节点-python

《剑指offer》python实现系列,全目录

最初思路:遍历,对已访问的结点做个标记,但不知道在不改变原链表的情况下怎么做标记.
书上的思路:例子见P139
step1:判断是否有环;
设立两个游标,一个移动两步,一个一次移动一步,若走的慢的追上走的快的,则有环。若直到末尾也没追上,则无环。

step2:确定环中的结点个数
在stepo1中,两个游标相遇的位置一定在环内,从该位置出发,记录走过的结点数,再次回到该位置就是环中结点的个数。

step3:判断入口结点的位置
假定环中结点的个数为N,设立两个游标,让一个从N处出发,一个从头结点出发,两个游标相遇的结点就是入口结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def EntryNodeOfLoop(self, pHead):
#step1 判断是否有环
p1 = pHead ##两个游标,p1一次一步,p2一次两步
p2 = pHead
flag = 0

while p2 != None and p2.next != None:
p1 = p1.next
p2 = p2.next.next
if p1 == p2:#相遇了,有环
temp = p1 #temp表示相遇的结点
while p1.next != temp:
p1 = p1.next
flag += 1 #统计环中结点个数
flag += 1
break
if flag == 0:
return None
else:
#step2确定环中结点的个数
#step3确定入口位置
p1=pHead
p2=pHead
for _ in range(flag):#让p2先走N个结点
p2 = p2.next
while p1 != p2:
p1 = p1.next
p2 = p2.next
return p1

其他方法:
用一个辅助列表保存已经遍历过的结点

1
2
3
4
5
6
7
8
def EntryNodeOfLoop(self, pHead):
saved = []
while pHead != None:
if pHead in saved:
return pHead
saved.append(pHead)
pHead = pHead.next
return None
if help:小手一抖点个广告 or 大手一挥资助一下