Find Loop in Linked List

# 問題

片連結リストが与えられたとき，そのリストがループしているか判定し，しているならどこでループしているのかを求めろ．

# 答え

2 つのポインタ！

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
def check_loop(head):
    faster = head
    slower = head
    while faster is not None and faster.next_node is not None:
        faster = faster.next_node.next_node
        slower = slower.next_node
        if faster is slower:
            break # there is a loop!

    if faster is None or faster.next_node is None:
        return (False, None)

    slower = head
    while slower is not faster:
        slower = slower.next_node
        faster = faster.next_node

    return (True, slower)