《剑指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):
p1 = pHead
p2 = pHead
flag = 0
while p2 != None and p2.next != None:
p1 = p1.next
p2 = p2.next.next
if p1 == p2:
temp = p1
while p1.next != temp:
p1 = p1.next
flag += 1
flag += 1
break
if flag == 0:
return None
else:
p1=pHead
p2=pHead
for _ in range(flag):
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
|
