cycled singly linked listのcycleがはじまったnodeを返すコードがインプット次第でアウトプットが異なる原因

Question

下記の問題に対して、間違えているコード がインプットデータが [1,2]0のときに失敗してしまいます。
原因をデバックをしながら特定しようとしていますが、見つけられずにいます。

もし、お気づきの点ありましたらご教示いただけませんしょうか？

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Do not modify the linked list.

引用元: 142. Linked List Cycle II

間違えているコード

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        idx_table = {}
        count = 0
        
        while head: # node1, node2, node1
            if idx_table.get(head, 0): # {}, {node1: 0}, {node1: 0, node2:1}
                return head
                
            idx_table[head] = count # {node1: 0}, {node1: 0, node2:1}
            head = head.next       # node2, node1
            count+=1 # 1, 2

アウトプット1(失敗)

Your input
[1,2]
0
Output
tail connects to node index 1
Expected
tail connects to node index 0

アウトプット2(成功)

Your input
[3,2,0,-4]
1
Output
tail connects to node index 1
Expected
tail connects to node index 1

下記の書き方では正解できてはいます。

正解のコード1

    
        seen = set()
        while head:
            if head in seen:
                return head
            seen.add(head)
            head = head.next

正解のコード2

        hash_map = {}
        while head:
            hash_map[head] = head
            if hash_map.get(head.next, 0):
                return head.next
            head = head.next

Comments

[kazuma-s]

デバッグするんだったら、デバッグするための実行可能なコードが必要です。
与えられた入力から、循環を持つ連結リストを構築しないといけないし、
循環を検出した後、結果の表示もあったほうがいいでしょう。
デバッグしようとしているコード全体を質問に書いてください。

Answer 1

原因は、間違っているコードで count = 0 としていることです。
各ノードに 0、1、2、... の番号を付与すると、
if idx_table.get(head, 0) で 0 が返ってきたときに
そのノード(head)が既に番号付けされたものかどうか判定できません。

count = 1 にするか、あるいは、idx_table[head] = count の前に
count += 1 を入れると正しくなるでしょう。

追記
count = 1 から始めて、各ノードに 1、2、3、... と番号を付ければいいのですが、
各ノードを 1、1、1、... としてもよいので、count += 1 は不要です。
dict を使って、key がノード、value が 1 ですが、その value は見ていません。
key が存在するかどうかだけを見ています。
ということで、dict を使う必要はなく、set で十分だということです。

Comments

[sequelanonymous]

完全に私の見落としでした。ご指摘ありがとうございます！助かります。