141. 环形链表
说明
给你一个链表的头节点 head ,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。
为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。
注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ,则返回 true 。 否则,返回 false 。
题解
通过快慢指针方式(慢指针一次走一步、快指针一次走两步),当快指针追上慢指针时,说明链表存在环。
原理说明
假设环的节点个数为N,慢指针一次走1步,快指针一次走2步,如果存在环,第N步后:
慢指针:N步
快指针:2N步
由于环的存在,两个指针必在N = 2N时重合。
代码
# Python3
# Definition for singly-linked list.
class ListNode:def __init__(self, x=None):self.val = xself.next = Noneclass Solution:def hasCycle(self, head: ListNode) -> bool:if head is None or head.next is None or head.next.next is None:# 只有一个节点,必不存在环# 两个节点,后一节点无后续节点,必不存在环return Falseslow, fast = head, head.nextwhile fast.next and fast.next.next:# 当不存在环时,快指针率先指空,跳出循环slow = slow.nextfast = fast.next.nextif slow == fast:return Truereturn False