【leetcode 142】 Linked List Cycle II 链表找环

el/2024/2/25 23:13:07

链表找环

https://leetcode.com/problems/linked-list-cycle-ii/

class Solution(object):def detectCycle(self, head):""":type head: ListNode:rtype: bool"""p1 = headp2 = headwhile p1 is not None and p1.next is not None:p1=p1.next.nextp2=p2.nextif p1==p2:breakif p1==None or p1.next==None:return Nonep1 = headwhile p1!=p2:p1=p1.nextp2=p2.nextreturn p1

解释:
在这里插入图片描述
快慢指针发,p1每次移动两个节点,p2每次移动一个节点,p1、p2必然相遇。相遇时如上图所示,另|AB|=l0,p1能追上p2说明p1比p2多走了整数倍的圈数,若假设一圈的长度为c,则 Δ l = k c \Delta l=kc Δl=kc,此时,从链表头到A的距离为 k c − l 0 kc - l_0 kcl0,同时p2到A的距离为 c − l 0 c-l_0 cl0,若让p1从表头开始以一次一个节点的速度移动,p2的速度不变,继续移动,p1、p2的相遇节点恰好为A,即环的起始节点(p2多走几圈无所谓)。


http://www.ngui.cc/el/4894911.html

相关文章

VirtualBox安装增强工具时:Unable to install guest additions: unknown filesystem type 'iso9660'

搬运一下答案(原文地址https://askubuntu.com/questions/596998/unable-to-install-guest-additions-unknown-filesystem-type-iso9660?newreg2d19e8256398418aa9fefb792def28a8),原因如答主所说。

【pyqt5】拖拽绘制矩形框

博主想自己做一个图片标注工具,用于制作目标检测数据集,其中一个功能就是拖拽鼠标选中矩形区域,参考了几篇博客,自己实现了一下,效果如下: 下面是实现: import sys,math from PyQt5.QtGui imp…

【numpy】ndarray交换两行(两列)、重新排列

numpy进行行(列)交换非常简便,因为numpy的下标访问是基于视图机制的,对子视图重新赋值即可。 a np.arange(12).reshape(3, 4) print(a) a[[0, 2]] a[[2, 0]] a运行结果: [[ 0 1 2 3][ 4 5 6 7][ 8 9 10 11]] array([[ 8, 9, 10, 11],[ 4, 5…

【python】python的for-else语法解释

若for循环正常结束,则执行else, 若for循环break,则不执行else。 for item in container:if search_something(item):# Found it!process(item)break else:# Didnt find anything..not_found_in_container()

【python】编码互转(16进制|bytes|base64|字符串)

基于python3 # 16进制转bytes byte_arr bytes.fromhex("1f2f3f4f") # bytes转16进制 byte_arr.hex() # bytes转base64,输入输出都是bytes import base64 base64.b64encode(byte_arr) # base64转bytes base64.b64decode(base64_byte_arr) # 字符串转byte…

【spark】spark dataframe空值·部分原因

数据类型不一致导致的空值 今天在写一个spark job(pyspark)时又遇到了,又遇到了数据处理的两大拦路虎之一的空数据问题,检查数据源,确定不会有空值后,开始检查代码。最终发现是代码之前的维护者使用了一个字符串作为一个long typ…

【git】强制使用远程分支(git pull -f ?)

git reset --hard origin/your-branch参考 https://stackoverflow.com/questions/1125968/how-do-i-force-git-pull-to-overwrite-local-files

oracle 导入DMP文件时IMP-00013: 只有 DBA 才能导入由其他 DBA 导出的文件 IMP-00000: 未成功终止导入

今天要导入一个人有别人发过来的数据库备份,结果出现如下问题: 百度了一下原因,主要是一个DBA用户权限问题,导出数据的用户拥有DBA权限,而我要导入的用户没有这个权限而已 解决的办法由两个,一个是把导出的…

设置MyEclipse 9/10中的html/JSP编辑自动提示

在myeclipse 9以前的版本中,我们如果要为html编辑器添加自动的代码提示可以这样操作: windows-->preferences-->MyEclipse-->Files andEditors-->HTML-->HTML Source-->Content assist 在右边的在Prompt when these characters are in…