はじめに

　leetcodeでアルゴリズムの勉強を始めた際、Linked list（連結リスト）というデータ構造について勉強したのでメモしました。

配列と連結リストの違い

配列と連結リストについては、以下の記事が参考になります。
https://qiita.com/BumpeiShimada/items/522798a380dc26c50a50

連結リストのイメージを掴むには、以下の記事が参考になります。
https://astrostory.hatenablog.com/entry/2020/02/24/070213

LeetCodeの問題を解いてみる

問題文の詳細は、leetcodeにアクセスして確認してみてください。
https://leetcode.com/problems/linked-list-cycle/

問題文の抜粋
Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

この問題では、与えられた連結リストが循環（ループ）している場合にTrueを返し、していない場合にFalseを返すという問題です。

この問題は他の記事でも解かれているのを見かけましたが、どういう風に連結リストを生成し、出力結果を返すかどうかという記事は見られなかったので、その部分の処理についても記述しました。

この問題で重要なのは、ListNodeで生成したノードオブジェクトのアドレスの繋がりを理解することです。

処理結果に関係のない部分はコメント文にしていますが、アドレスの繋がりを理解するためには適宜コメント文を外して確認すると良いと思います。

解法1 (HashSetを利用)

この解き方では、空集合にノードオブジェクト（アドレス）を頭から順番に追加していきます。集合に追加しようと思ったノードオブジェクトが既に入っていた場合、連結リストは循環しているとみなします。


class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
  def hasCycle(self, head):
    seen = set()
    curr = head
    # print(curr)
    while curr: # currがNoneでない限りループ
      if curr in seen:
        # print(curr)
        return True
      seen.add(curr)
      # print(seen)
      curr = curr.next
      # print(curr)
    return False

# head = [3,2,0,-4]
# pos = 1 # posはパラメータではなく、最後の要素がどこに戻るかを示す。（この場合、最後の-4は１番目の要素の2に戻る）

# 循環する連結リストの作成
links = ListNode(3)
# print(vars(links))
links.next = ListNode(2)
# print(vars(links))
# print(vars(links.next))
links.next.next = ListNode(0)
# print(vars(links.next))
# print(vars(links.next.next))

links.next.next.next = ListNode(-4)
links.next.next.next.next = links.next # 2に戻る(循環させる)
# print(vars(links.next.next.next))
# print(vars(links.next.next.next.next)) # 循環を確認
# print(vars(links.next.next.next.next.next))

obj = Solution()
print(obj.hasCycle(links)) # 循環している場合、True

解法2 (速度の違うポインタを利用)

この解き方では、一つ一つノードを遷移するslowと、一つ飛ばしでノードを遷移するfastというポインタを用意します。連結リストが循環している場合、異なる速度で遷移するslowとfastはやがて同じアドレスを指します。このことより、循環しているかを判断します。


class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head: # leetcodeではtestcaseにnullを含む場合あるので記述
            return False
        slow = head #一つ先のポインタへ
        fast = head.next #二つ先のポインタへ
        # print(slow, fast)
        while slow != fast: # slowとfastが同じアドレスを指さない限りループ（循環していれば、速度の違うslowとfastはいずれ同じアドレスを指す）
            if not fast or not fast.next: # fastとfastの次がnullの場合はlinked-listは終わっているのでFalseを返す
                return False
            slow = slow.next
            fast = fast.next.next
            print(slow, fast)
        return True # slowとheadが同じノードに到達すればループ

# head = [3,2,0,-4]
# pos = 1 # posはパラメータではなく、最後の要素がどこに戻るかを示す。（この場合、最後の-4は１番目の要素の2に戻る）

# 循環ex
links = ListNode(3)
# print(vars(links))
links.next = ListNode(2)
# print(vars(links))
# print(vars(links.next))
links.next.next = ListNode(0)
# print(vars(links.next))
# print(vars(links.next.next))

links.next.next.next = ListNode(-4)
links.next.next.next.next = links.next # 2に戻る(循環させる)
# print(vars(links.next.next.next))
# print(vars(links.next.next.next.next)) # 循環を確認
# print(vars(links.next.next.next.next.next))

# 最初のslowとfastのアドレスがそれぞれlinksとlinks.nextに一致するか確認
# print(links)
# print(links.next)

obj = Solution()
print(obj.hasCycle(links)) # 循環している場合、True
# 遷移の確認
# slow(一個一個進む)：3,2,0,-4
# fast（一つとばし）: 2,-4,0 (2,0,-4でループより)
# よって、slowとfastは２回の遷移で同じノード０のアドレスになり、循環を確認

追記

連結リストの作成は、以下のようにループ処理でも可能です。上記のlinksがheadに対応しています。


# 循環する連結リストの作成方法2
data = [3,2,0,-4]
# pos = 1 # posはパラメータではなく、最後の要素がどこに戻るかを示す。（この場合、最後の-4は１番目の要素の2に戻る）

# ループで連結リストを作成
tail = head = ListNode(data[0])
for i in data[1:]:
    tail.next = ListNode(i) # アドレスは１回目でhead.next、２回目でhead.next.next,3回目でhead.next.next.next
    tail = tail.next

head.next.next.next.next = head.next

# # 確認
# print(vars(head))
# print(vars(head.next))
# print(vars(head.next.next))
# print(vars(head.next.next.next))
# print(vars(head.next.next.next.next))

まとめ

最初、アドレスの遷移をイメージするまでに時間がかかったが、わかると結構単純でした。leetcodeを利用してどんどんアルゴリズムの勉強を進めていきたいです。

参考