チェーンテーブルにループがあるかどうかを判断し、ループノード--python実装を見つけます.
スナップポインタの方法で.時間複雑度O(n),空間複雑度O(1).
p 1をスローポインタとし、p 2をクイックポインタとし、両者は初期にチェーンテーブルのヘッダノードを指し、スローポインタp 1は1ステップずつ前進し、クイックポインタp 2は2ステップずつ前進する.チェーンテーブルにリングが存在する場合、速いポインタp 2は必ず先にリングに入り、遅いポインタp 1の後にリングに入り、2つのポインタは必ず出会う.ループが存在しない場合、スナップポインタはチェーンテーブルの末尾に先行してNoneになります.
p 1をスローポインタとし、p 2をクイックポインタとし、両者は初期にチェーンテーブルのヘッダノードを指し、スローポインタp 1は1ステップずつ前進し、クイックポインタp 2は2ステップずつ前進する.チェーンテーブルにリングが存在する場合、速いポインタp 2は必ず先にリングに入り、遅いポインタp 1の後にリングに入り、2つのポインタは必ず出会う.ループが存在しない場合、スナップポインタはチェーンテーブルの末尾に先行してNoneになります.
class LNode:
def __init__(self, val):
self.val = val
self.next = None
# ,
# , , ,
def exit_loop(LList):
p1 = p2 = LList
# , , False
while p2 and p2.next:
p1 = p1.next
p2 = p2.next.next
if p1 == p2:
return True
return False
# ,
# , , , 1 ,
def find_entry_of_loop(pHead):
if not pHead:
return None
slow = pHead
fast = pHead
while slow.next and fast.next.next:
slow = slow.next
fast = fast.next.next
# , ,
if fast == slow:
break
# ,
if not fast or not fast.next:
return None
slow = pHead
# 1, ,
while slow != fast:
slow = slow.next
fast = fast.next
return slow
if __name__ == "__main__":
LList = LNode(0)
p1 = LNode(1)
p2 = LNode(2)
p3 = LNode(3)
p4 = LNode(4)
p5 = LNode(5)
LList.next = p1
p1.next = p2
p2.next = p3
p3.next = p4
p4.next = p5
p5.next = p2
print (exit_loop(LList))
print (find_entry_of_loop(LList).val)