Python程序检测链表中的循环

1. 什么是链表循环

在开始讨论 Python程序检测链表中的循环之前,我们先来说一下链表循环的概念。链表循环是指链表中某个节点指向链表中已经出现过的另一个节点,形成一个环的情况。例如下图所示:

2. Python程序检测链表中的循环的实现思路

检测链表中的循环有多种实现思路,下面我们介绍一种较为简单的思路。

2.1 快慢指针法

快慢指针法是检测链表中是否存在循环的一种方法。该方法的基本思路是:设置两个指针(一个快指针和一个慢指针),快指针每次向前移动两个节点,慢指针每次向前移动一个节点。如果链表中不存在循环,则快指针会先到达链表末尾;如果链表中存在循环,则快指针会在某一时刻与慢指针相遇。

具体实现代码如下:

class Node:

def __init__(self, val):

self.val = val

self.next = None

def has_cycle(head: Node) -> bool:

"""

判断链表是否有循环

:param head: 链表头节点

:return: boolean

"""

if not head:

return False

slow = head

fast = head

while fast and fast.next:

slow = slow.next

fast = fast.next.next

if slow == fast:

return True

return False

在上面这段代码中,我们定义了一个有两个属性的类 Node,属性 val 代表链表中的值,属性 next 代表链表中的下一个节点。接着我们定义了一个函数 has_cycle,该函数用于判断链表是否有循环。其实现思路就是上文所提到的快慢指针法。需要注意的是,如果链表为空,则认为链表不存在循环。

3. 测试实例

我们来测试一下上面的 Python程序检测链表中的循环的实现:

n1 = Node(3)

n2 = Node(2)

n3 = Node(0)

n4 = Node(-4)

n1.next = n2

n2.next = n3

n3.next = n4

n4.next = n2

print(has_cycle(n1)) # True

在上面的测试实例中,我们创建了一个环形链表,并使用上面实现的 has_cycle 函数进行判断,得到的结果为 True,证明函数判断的正确性。

4. 总结

本文介绍了 Python程序检测链表中的循环的实现思路,主要是快慢指针法,并给出了测试实例。需要注意的是,在实现时要注意链表为空的情况,不然会导致程序出错。

后端开发标签