チェーンテーブルにループがあるかどうかを判断し、ループノード--python実装を見つけます.


スナップポインタの方法で.時間複雑度O(n),空間複雑度O(1).
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)