Hot-141 环形链表判断

1、解法1：set 判断是否visited

# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: # 环形链表判断： # 节点范围[0,10e4] # 解法1：哈希set visited = set() if head == None: return False if head.next == head: return True node = head while node != None: if node in visited: return True else: visited.add(node) node = node.next return False

2、解法2：快慢指针，迟早追上

# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: # 环形链表判断： # 节点范围[0,10e4] # 解法1：哈希set # 解法2：时间O(n),空间O(1), 快慢指针 if head == None: return False if head.next == head: return True # 迟早追上 slow,fast = head,head while fast != None and fast.next!=None: fast = fast.next.next slow = slow.next if slow == fast: return True return False