题目
给定一个链表,判断链表中是否有环。
为了表示给定链表中的环,我们使用整数 pos
来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos
是 -1
,则在该链表中没有环。
示例 1:
输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。
示例 2:
输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。
示例 3:
输入:head = [1], pos = -1
输出:false
解释:链表中没有环。
代码
使用快慢指针
- 慢指针每次走一步
- 快指针每次走两步
若快慢指针相遇,则说明存在环,否则不存在环
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def hasCycle(head):
"""快慢指针"""
if head is None or head.next is None:
return False
slow = head # 慢指针,初始=head,相当于从哨兵节点走一步
fast = head.next # 快指针,初始=head.next,相当于从哨兵节点走两步
while slow is not None and fast is not None and fast.next is not None:
if slow == fast: # 快慢指针相遇
return True # 说明存在环
slow = slow.next # 慢指针走一步
fast = fast.next.next # 快指针走两步
return False
if __name__ == "__main__":
# nums = [3, 2, 0, 4]
# pos = 1
# nums = [1, 2]
# pos = 0
nums = [1]
pos = -1
pre_head = ListNode(x=None) # 哨兵节点
pre_node = pre_head
for idx in range(len(nums)):
node = ListNode(x=nums[idx])
pre_node.next = node
pre_node = pre_node.next
if pos != -1:
node = pre_head.next
for i in range(pos):
node = node.next
pre_node.next = node
print(hasCycle(pre_head.next))