環形鏈表
題目來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/linked-list-cycle-ii
目前考慮到兩種解法，但都需要輔助空間， 第一種 O(n) 第二種 O(1)
第一種 借助輔助字典進行判斷
將走過的節點都記錄在字典中，通過查詢字典的key值是否存在來確定是否有環
時間復雜度為 O(n) , 空間復雜度為 O(n)
代碼如下：
# -*- coding: utf-8 -*-
# @Author : xaohuihui
# @Time : 19-12-6
# @File : detect_cycled.py
# Software : study
"""
檢測環形鏈表
"""
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def has_cycle(head: ListNode) -> bool:
dict_node = dict()
i = 0
if head and head.next:
while head and head.next:
id_head = str(id(head))
if dict_node.get(id_head) is None:
dict_node[id_head] = i
else:
return True
i += 1
head = head.next
return False
else:
return False
if __name__ == '__main__':
# head=[3,2,0,4] pos= 1
node1 = ListNode(3)
node2 = ListNode(2)
node3 = ListNode(0)
node4 = ListNode(4)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node2
print(has_cycle(node1))輸出如下：
True
第二種解法 快慢指標
# -*- coding: utf-8 -*-
# @Author : xaohuihui
# @Time : 19-12-6
# @File : detect_cycled.py
# Software : study
"""
檢測環形鏈表
"""
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
# 第二種解法
def has_cycle(head: ListNode) -> bool:
if head and head.next:
fast = slow = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if fast == slow:
return True
else:
return False
if __name__ == '__main__':
# head=[3,2,0,4] pos= 1
node1 = ListNode(3)
node2 = ListNode(2)
node3 = ListNode(0)
node4 = ListNode(4)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node2
print(has_cycle(node1))
輸出結果
True
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/117887.html
標籤：其他
上一篇：CTF萌新對逆向的疑惑
下一篇：如何創建｛自動生成模組｝