首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

测试链表是否有循环的最佳算法

测试链表是否有循环的最佳算法是Floyd's Cycle-Finding Algorithm,也被称为“乌龟与兔子赛跑算法”。该算法使用两个指针,一个快指针和一个慢指针,同时遍历链表。快指针每次移动两个节点,慢指针每次移动一个节点。如果链表中存在循环,那么快指针和慢指针最终会相遇;如果链表中不存在循环,那么快指针会先到达链表的末尾。

以下是使用Floyd's Cycle-Finding Algorithm测试链表是否有循环的Python代码示例:

代码语言:python
代码运行次数:0
复制
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def hasCycle(head: ListNode) -> bool:
    slow = head
    fast = head

    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            return True

    return False

在这个示例中,我们定义了一个ListNode类来表示链表中的节点。hasCycle函数接受一个链表的头节点作为参数,并返回一个布尔值,表示链表是否有循环。在函数中,我们使用两个指针slowfast,分别初始化为链表的头节点。然后,我们在循环中遍历链表,每次迭代中,慢指针slow向前移动一个节点,快指针fast向前移动两个节点。如果链表中存在循环,那么快指针和慢指针最终会相遇,函数返回True;否则,如果快指针到达链表的末尾,函数返回False

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

5分36秒

2.19.卢卡斯素性测试lucas primality test

5分10秒

2.18.索洛瓦-施特拉森素性测试Solovay-Strassen primality test

6分47秒

2.1.素性检验简介

7分58秒
4分28秒

2.20.波克林顿检验pocklington primality test

1分36秒

智慧工地设备监控系统

1分28秒

人脸识别安全帽识别系统

2分7秒

基于深度强化学习的机械臂位置感知抓取任务

领券