首页 > 编程语言 >[Python手撕]环的检测

[Python手撕]环的检测

时间:2024-08-31 11:38:25浏览次数:9  
标签:head slow Python 检测 fast next 链表 指针

检测环

快慢指针法是一种用于检测链表中是否存在环的有效方法,同时也可以找到环的起点。该方法的原理基于两个指针在链表上同时移动,其中一个移动得更快,而另一个移动得更慢。

  1. 检测环的存在:

    • 使用两个指针,一个称为快指针(fast),一个称为慢指针(slow)。
    • 在每一步中,快指针向前移动两步,而慢指针只移动一步。
    • 如果链表中不存在环,那么快指针最终会到达链表的尾部,此时可以确定链表中无环。
    • 如果链表中存在环,由于快指针的速度比慢指针快,它们最终会相遇。
  2. 找到环的起点:

    • 一旦快慢指针相遇,说明链表中存在环。
    • 将其中一个指针(例如慢指针)重新移到链表的头部,保持另一个指针在相遇点。
    • 然后,两个指针以相同的速度前进,直到它们再次相遇。这次相遇点就是环的起点。

为什么这个方法有效?

  • 如果链表中不存在环,快指针将最终到达链表的尾部,而慢指针也会到达链表的末尾。由于没有环,两者不会相遇。
  • 如果链表中存在环,快慢指针最终会在环中的某一点相遇。此时,将其中一个指针移到链表头部,它们再次相遇的地方就是环的起点。

这个方法的时间复杂度为O(N),其中N是链表的长度。因为快指针每次移动两步,而慢指针每次移动一步,所以快指针最多需要N/2步就能遇到慢指针。在找到相遇点后,重新移动指针的过程最多需要再走N步。

证明

让我们来证明一下,为什么上面两个说法是正确的。

首先,进入环之前的路越长,快慢指针之间的差距就越大,如果这段路足够长,甚至会出现快指针已经在环里面走了好几圈,但是慢指针还没有进入环的情况。

但是不管前面的路有多长,不管慢指针进入环的时候,快指针在环的哪个位置,慢指针进入环以后,快指针总是可以在慢指针走不到一圈的时候追上他,因为慢指针在环内走了一圈的时候,快指针已经走了两圈,一定可以追得上。

image

下面我们来列算式

进入环之前的路长度为:P

慢节点在环内走过的路为:S

环的总长度为:C

慢指针总共走过的长度:P+S

那么快指针走过的总长度:2(P+S)

快指针在环内走过的长度:P+2S

快慢指针相遇的时候,他们处在同一个位置上:S%C = (P+2S)%C

化简,(P+S)%C = 0,也就是说(P+S) = NC

现在我们在位置S上,再走P的长度就可以回到环的起点。

先来看如何判断是否有环

Leetcode 141. 环形链表

给你一个链表的头节点 head ,判断链表中是否有环。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ,则返回 true 。 否则,返回 false 。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head:
            return False
        fast = head
        slow = head
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                return True
        return False

再来看环的起点在哪里

LCR 022. 环形链表 II

给定一个链表,返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环,则返回 null。

为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意,pos 仅仅是用于标识环的情况,并不会作为参数传递到函数中。

说明:不允许修改给定的链表。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if not head:
            return False

        fast = head
        slow = head

        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next

            if fast == slow:
                fast = head
                while fast != slow:
                    fast = fast.next
                    slow = slow.next  
                return fast
        return False

标签:head,slow,Python,检测,fast,next,链表,指针
From: https://www.cnblogs.com/DCFV/p/18390040

相关文章

  • [Python手撕]二分法
    二分法二分法的几个位置比如01234567891233333456有时候想要寻找小于3的最大数字有时候想要寻找第一个满足>=3的数字,有时候想要寻找最后一个满足>=3的数字,有时候想要寻找小于4的最大数字nums=[1,2,3,4,5,5,5,5,5,6,7,8,9]n=......
  • [Python手撕]TOPK
    TOPK问题描述:从arr[1,n]这n个数中,找出最大的k个数,这就是经典的TopK问题。栗子:从arr[1,12]={5,3,7,1,8,2,9,4,7,2,6,6}这n=12个数中,找出最大的k=5个。整体排序排序是最容易想到的方法,将n个数排序之后,取出最大的k个,即为所得。伪代码:sort(arr,1,n);returnarr[1,k];......
  • 豆包 API 调用示例代码详解-Python版
    文章目录豆包API调用示例代码详解-Python版一、事前准备二、所需Python包三、代码详解五、源码下载四、总结豆包官方API文档豆包API调用示例代码详解-Python版在本文中,我们将详细介绍如何使用Python调用豆包API,并提供相关的事前准备和代码执行步骤。一、......
  • 网络安全公开数据集Maple-IDS,恶意流量检测数据集开放使用!
    MapleDataset枫叶数据集MapleDataset枫叶数据集由东北林业大学网络安全实验室(https://maple.nefu.edu.cn/lab/)公开发布,是用于入侵检测评估的数据集,其目的在于提升异常基础入侵检测系统(IDS)以及入侵预防系统(IPS)的性能与可靠性。在网络攻击愈发复杂的当下,拥有一个可靠且紧跟时代的......
  • 使用 Python 实现自动化办公
    使用Python实现自动化办公在现代办公环境中,自动化是提高工作效率和减少人为错误的重要手段之一。Python是一种功能强大且灵活的编程语言,可以轻松地实现自动化办公任务。下面是一个简单的示例,展示如何使用Python实现自动化办公:需求:假设我们有一个Excel文件,名为"报表.xls......
  • [Python办公]一文入门图论Graphs,轻松处理最短路径等问题!
            [Python办公]一文入门图论Graphs,轻松处理最短路径等问题!        图论是研究图这种数学结构的性质和应用的学科。图(Graphs)由节点(或顶点)和连接这些节点的边组成,它是一种强大的数据结构,广泛应用于各种领域。以下举例用最短距离来入门图论。入门问题: ......
  • Python数据清洗基础
    在Python中进行数据清洗和可视化是一个多步骤的过程,涉及到数据的读取、预处理、分析和图形表示。以下是一些关键步骤和代码示例,这些步骤可以帮助你从原始数据中提取有价值的信息,并以直观的方式展示。数据清洗读取数据:importpandasaspddata=pd.read_csv('data.csv')处......
  • [Python知识点]list列表append()和extend()的区别
    在Python中,list.append()和list.extend()都是列表(list)的方法,用于添加元素,但它们的工作方式有所不同:list.append(x):这个方法将对象x添加到列表的末尾。x可以是任何数据类型,包括列表。如果x是一个列表,那么这个列表会被作为一个单个元素添加到原列表的末尾。list.extend(itera......
  • 6种有效的时间序列数据特征工程技术(使用Python)
    在商业分析中,"时间"是一个核心概念。我们基于时间组件来分析销售数据、收入、利润、增长,甚至进行预测。然而,对于初学者来说,这可能是一个复杂的主题。在处理时间敏感的数据集时,需要考虑时间序列数据的多个细微方面。在这个领域,没有放之四海而皆准的方法。我们不必总是强制使用传......
  • python学习总结--面向对象
    1.面向对象(上)1.1定义面向对象编程:oop[objectorientedprogramming]是一种python的编程思路;面向过程:就是我们一开始学习的,按照解决问题的步骤去写代码【根据业务逻辑去写代码】,在思考问题的时候,首先分析'怎么按照步骤去实现'然后将问题解决拆解成若干个步骤,并将这些步骤对......