Leetcode # 142. Linked List Cycle II (Floyd’s Tortoise🐢 and Hare🐇)

https://leetcode.com/problems/linked-list-cycle-ii/

First Solution

Time Complexity: O(length(list))
Space Complexity: O(length(list))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
    appeared_node = set()
    cur = head
    while(cur):
      if cur in appeared_node:
        return cur
      appeared_node.add(cur)
      cur = cur.next
    return None

Better Solution: Floyd’s Tortoise🐢 and Hare🐇

Floyd’s Cycle Detection Algorithm / Tortoise and Hare Algorithm

Time Complexity: O(len(linked_list))
Space Complexity: O(1)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
    # step 1
    hare = tortoise = head
    while hare is not None and tortoise is not None:
      hare = hare.next
      if hare: hare = hare.next
      tortoise = tortoise.next
      if hare == tortoise: break

    if hare is None: return None

    # step 2
    tortoise = head
    while hare != tortoise:
      hare = hare.next
      tortoise = tortoise.next

    return hare

相關例題

Leetcode # 141. Linked List Cycle

Last Updated on 2023/08/16 by A1go