#4/20 Linked Lists: Detect a Cycle [Cracking the Coding Interview Challenges]

#4 Linked Lists: Detect a Cycle

www.hackerrank.com

linked lists(連結リスト)を題材にした問題。 リストを走査中にいずれかのノードが1回以上訪問された場合、trueを、それ以外の場合はfalse を返す。

solution

解答可能な言語選択にrubyがなかったため、今回はpythonで解いた。

def has_cycle(head):
    s = set()
    while head:
        if head in s:
            return True
        s.add(head)
        head = head.next

    return False

github.com

Linked Lists(連結リスト)とは

一連のノードが、任意のデータフィールド群を持ち、1つか2つの参照(リンク)により次(および前)のノードを指している。連結リストの主な利点は、リスト上のノードを様々な順番で検索可能な点である。連結リストは自己参照型のデータ型であり、同じデータ型の別のノードへのリンク(またはポインタ)を含んでいる。連結リストは場所が分かっていれば、ノードの挿入や削除を定数時間で行うことができる(場所を探すのにかかる時間はリスト上の順番の条件などにも依存するし、後述する片方向リストなのか双方向リストなのかにも依存する)。連結リストにはいくつかの種類があり、片方向リスト、双方向リスト、線形リスト、循環リストなどがある。

連結リスト - Wikipedia