NC4 判斷連結清單中是否有環 python

描述

判斷給定的連結清單中是否有環。如果有環則傳回true，否則傳回false。

資料範圍：連結清單長度 0 ≤ n ≤ 10000 0 \leq n \leq 10000 0≤n≤10000

要求：空間複雜度 O ( 1 ) O(1) O(1)，時間複雜度 O ( n ) O(n) O(n)

輸入分為2部分，第一部分為連結清單，第二部分代表是否有環，然後回組成head頭結點傳入到函數裡面。-1代表無環，其他的數字代表有環，這些參數解釋僅僅是為了友善讀者自測調試。實際在編碼時讀入的是連結清單的頭節點。

示例1

輸入：{3,2,0,-4},1

傳回值：true

說明：第一部分{3,2,0,-4}代表一個連結清單，第二部分的1表示，-4到位置1，即-4->2存在一個連結，組成傳入的head為一個帶環的連結清單 ,傳回true

示例2

輸入：{1},-1

傳回值：false

說明：第一部分{1}代表一個連結清單，-1代表無環，組成傳入head為一個無環的單連結清單，傳回false

示例3

輸入：{-1,-7,7,-4,19,6,-9,-5,-2,-5},6

傳回值：true

Python實作

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

#
# 
# @param head ListNode類 
# @return bool布爾型
#
class Solution:
    def hasCycle(self , head ):
        # write code here
        # 判斷連結清單是否為空，或隻有一個Node
        if head is None or head.next is None:
            return False
        else:
            # 建立一個空list，用來存放每個Node
            # 如果某個Node被再次放入，則存在有環
            # cache = []
            cache = set() # 用set比list更快
            while head:
                # 在cache中則存在有環
                if head in cache:
                    return True
                # 不在cache中則放入
                # cache.append(head)
                cache.add(head)
                head = head.next
            return False
#         slow = head
#         fast = head
#         while (fast != None and fast.next != None):
#             slow = slow.next
#             fast = fast.next.next
#             if fast == slow:
#                 return True
#         return False
           

使用set的效率（時間快，但空間消耗大）：

使用list的效率（時間慢，但空間消耗小）：

不使用新空間的效率（時間快，空間消耗也小）：