141. 環形鏈表

方法一

• 核心思想：

  • 使用一個集合?seen?來記錄已經訪問過的節點。
  • 遍歷鏈表，如果當前節點已經存在于集合中，說明鏈表存在環；否則，將當前節點添加到集合中，繼續遍歷。
  • 如果遍歷結束（head?為?None），說明鏈表沒有環。

• 時間復雜度：

  • 最壞情況下需要遍歷整個鏈表，時間復雜度為?O(n)，其中?n?是鏈表的節點數。

• 空間復雜度：

  • 使用了一個集合?seen?來存儲節點，空間復雜度為?O(n)。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution(object):def hasCycle(self, head):""":type head: ListNode:rtype: bool"""seen = set()while head:if head in seen:return Trueseen.add(head)head = head.nextreturn False

方法二

• 快慢指針的核心思想：

  • 快指針每次移動兩步，慢指針每次移動一步。
  • 如果鏈表存在環，快指針最終會追上慢指針（相遇）。
  • 如果鏈表不存在環，快指針會先到達鏈表末尾。

• 時間復雜度：O(n)。

• 空間復雜度：O(1)。

def hasCycle(self, head):slow = fast = head  # 初始化慢指針和快指針，都指向鏈表頭節點while fast and fast.next:  # 當快指針及其下一個節點不為空時slow = slow.next  # 慢指針每次移動一步fast = fast.next.next  # 快指針每次移動兩步if slow == fast:  # 如果快慢指針相遇return True  # 說明鏈表存在環return False  # 遍歷結束，沒有發現環