寫在開頭

今天選了141這題,想複習一下linked list的概念

進入正題

第141的題目如下:

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.
Example 2:
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.
Example 3:
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

這題開頭有說,linked list都是從陣列最後一個元素指向輸入指定的位置,如果輸入指定的位置是-1的話要return false
所以我想一開始應該先判斷輸入列表的長度,和指定位置是否可以形成linked list
不過題目是這樣寫的

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

沒看出來舉例時說輸入指定的位置是怎麼傳入的,所以...還是先研究下別人都怎麼解這題的@@
參考1連結裡提供的解法1

def hasCycle(self, head):
    map = {}
    while head:
        if id(head) in map:
            return True
        else:
            map[id(head)] = True
        head = head.next
    return False

他寫這個做法的意思是,按照輸入的走過一圈,確認能連成一個環的話,就回true;反之就回false
我試著加了print紀錄例子1輸入的測試結果

不過我不太理解的是,在例子1中,pos設定成"3"和"-1"的結果會不一樣


我一開始以為指定位置不能是-1的原因是因為linked list的節點都不能指向自己,
所以不管pos設定"3"或"-1"應該都要回false才對
但從print列印的紀錄上看,pos設定成"-1"的那個紀錄,在下一個id(head)會不在輸入的head裡面
可能指向的記憶體位置不一樣?要找說明研究研究...

參考資料

參考1141. Linked List Cycle [easy] (Python)