《剑指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
|