給定一個鏈表，判斷鏈表中是否有環(huán)隅肥。
為了表示給定鏈表中的環(huán)竿奏，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1武福，則在該鏈表中沒有環(huán)议双。
示例 1：
輸入：head = [3,2,0,-4], pos = 1
輸出：true
解釋：鏈表中有一個環(huán)痘番，其尾部連接到第二個節(jié)點(diǎn)捉片。
示例 2：
輸入：head = [1,2], pos = 0
輸出：true
解釋：鏈表中有一個環(huán)，其尾部連接到第一個節(jié)點(diǎn)汞舱。
示例 3：
輸入：head = [1], pos = -1
輸出：false
解釋：鏈表中沒有環(huán)伍纫。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/linked-list-cycle
給定一個鏈表，判斷鏈表中是否有環(huán)昂芜。
為了表示給定鏈表中的環(huán)莹规，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1泌神，則在該鏈表中沒有環(huán)良漱。
示例 1：
輸入：head = [3,2,0,-4], pos = 1
輸出：true
解釋：鏈表中有一個環(huán)，其尾部連接到第二個節(jié)點(diǎn)欢际。
示例 2：
輸入：head = [1,2], pos = 0
輸出：true
解釋：鏈表中有一個環(huán)母市，其尾部連接到第一個節(jié)點(diǎn)。
示例 3：
輸入：head = [1], pos = -1
輸出：false
解釋：鏈表中沒有環(huán)损趋。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/linked-list-cycle
class Solution():
def hasCycle_hash(self, head): # hash
s = set()
tmp = head
while tmp:
if tmp in s:
return True
else:
s.add(tmp)
tmp = tmp.next
return False
def hasCycle_fast_slow_point(self, head): #快慢指針
#沒有考慮鏈表長度小于2的情況
slow = fast = head
while slow != None and fast != None:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
# else:
# if fast != None:
# fast = fast.next
return False
class Node():
def init(self, val):
self.val = val
self.next = None
class SingleLinkList():
def init(self):
self.head = None
def is_empty(self):
if self.head == None:
return True
def length(self):
cur = self.head
count = 0
while cur != None:
cur = cur.next
count +=1
return count
def travel(self):
cur = self.head
while cur != None:
print(cur.val, end=' ')
cur = cur.next
print('\n')
def append(self, item):
node = Node(item)
cur = self.head
if self.is_empty():
self.head = node
else:
while cur.next != None:
cur = cur.next
cur.next = node
def reverseList(self):
# if self.head == None or self.head.next == None:
# return self.head
pre = None
cur = self.head
while cur != None:
next = cur.next
cur.next = pre
pre = cur
cur = next
self.head = pre
def addCycle(self, pos):
count = 0
cur = self.head
prev = self.head
end = self.head
while end.next != None:
if count != pos:
cur = cur.next
count += 1
end = end.next
end.next = cur
if name == 'main':
sll = SingleLinkList()
for i in range(1,11):
sll.append(i)
sll.travel()
sll.reverseList()
sll.travel()
sll.addCycle(3)
sll.travel() 不能運(yùn)行患久，會死循環(huán)的
s = Solution()
print(f'Has cycle?(Hash): {s.hasCycle_hash(sll.head)}')
print(f'Has cycle?(Slow Fast point): {s.hasCycle_fast_slow_point(sll.head)}')
