【Leetcode解題】141. Linked List Cycle

題目

• 題目連結
• 目標函式 : hasCycle(head)
  • Input : head: ListNode
  • Output : bool

解題概念

• 題意 : 給予一 Linked List head，判斷其中是否有 Cycle
• 這題也是在 Linked List 應用方面很常見的一題，相關題型可以參考 刷題筆記｜Leetcode — Linked List Cycle 題組

我的寫法

• 想法 : 利用雙重指標 oneStep 與 twoStep
  • oneStep : 一次往前一個節點
  • twoStep : 一次往前兩個節點
  • 如果在 oneStep 與 twoStep 都可以前進的狀況下，oneStep 與 twoStep 各自前進後發現皆指向同一節點，則代表 Linked List 中有 Cycle
• 程式碼 :

  def hasCycle(self, head):
      
      oneStep = head
      twoStep = head
  
      while oneStep != None and twoStep != None and twoStep.next != None:
          oneStep = oneStep.next
          twoStep = twoStep.next.next
  
          if oneStep == twoStep:
              return True
  
      return False

• 成效 :
  • Time Complexity : $\color{DB4D6D}{O(n)}$
  • Runtime: 36 ms (faster than 91.12%)
  • Memory Usage: 20.3 MB (more than 65.18%)

解答 or 其他優秀寫法

• 概念上都與我相同