Python中链表的环检测（Cycle Detection）算法

2023-04-11 00:00:00 算法 检测 链表

链表的环检测算法是指判断一个链表中是否存在环，如果存在环则返回True，否则返回False。这个算法可以通过快慢指针来实现。

具体实现步骤如下：

  1. 定义两个指针slow和fast，初始值都为链表的头节点。
  2. slow指针每次移动一个节点，fast指针每次移动两个节点。
  3. 如果链表中存在环，那么fast指针最终会追上slow指针，并且两个指针相遇的节点一定在环中。
  4. 如果链表中不存在环，那么fast指针会先遍历到链表结尾。如果在遍历过程中fast指针已经到达了链表结尾，说明链表没有环。

下面是Python代码演示：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def hasCycle(head: ListNode) -> bool:
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

# 创建一个有环的链表
node1 = ListNode('p')
node2 = ListNode('i')
node3 = ListNode('d')
node4 = ListNode('a')
node5 = ListNode('n')
node6 = ListNode('c')
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
node5.next = node6
node6.next = node3

print(hasCycle(node1))  # 输出 True

这个例子中，我们创建了一个有环的链表，并用hasCycle函数来检测是否存在环。最终输出结果为True，说明该链表存在环。

相关文章