LeetCode:142:环形链表 II(链表系列)
创始人
2025-05-29 05:22:08
0次

题目描述:给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

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

不允许修改链表

在这里插入图片描述

核心思想:快慢指针(slow指针每次移动一步,fast指针每次移动两次) + 寻找数学关系;

在这里插入图片描述

slow 和 fast 指针相遇走的长度:

slow指针运动长度:slow_length = x + y

fast指针运动长度:fast_length = x + y + n(y + z)

因为fast运动是slow运动的2倍,那么fast_length = 2*slow_length;

即 2(x + y) = x + y + n(y + z) ======> x = (n-1)(y + z) + z

当 n为1的时候,公式就化解为 x = z,

这就意味着,从头结点出发一个指针,从相遇节点 也出发一个指针,这两个指针每次只走一个节点, 那么当这两个指针相遇的时候就是 环形入口的节点。

问题:那么 n如果大于1在这里插入代码片是什么情况呢,就是fast指针在环形转n圈之后才遇到 slow指针。

​ 其实这种情况和n为1的时候 效果是一样的,一样可以通过这个方法找到 环形的入口节点,只不过,fast指针在环里 多转了(n-1)圈,然后再遇到slow,相遇点依然是环形的入口节点。

public class Solution {public static ListNode detectCycle(ListNode head) {// 快慢指针ListNode slow = head;ListNode fast = head;// 因为fast每一次移动2步,所以要对fast.next进行判断,如果fast.next为空,那么fast.next.ntxt就会报错while (fast != null && fast.next != null){slow = slow.next;  // 慢指针每一次只移动1次fast = fast.next.next;  // 快指针每一次移动2次if(slow == fast){  // 指针相遇,确定有环while(true){if(head == fast){return fast;}head = head.next;fast = fast.next;}}}return null;}
}

相关内容

热门资讯

在大吉订购APP订购交易亏损被...   近期,不少投资者反映在“大吉订购App”上投资白银、铂金等商品遭遇严重亏损。该平台宣称提供现货订...
铂银壹号APP商品订购交易亏损...   许多中小投资者误以为网上的“商品现货订购”是合规合法的理财渠道,殊不知这背后隐藏着巨大的合规风险...
兴鑫淘金APP贵金属订购交易亏...   白银、贵金属或其他商品类投资,除国家批准的正规期货交易场所及持牌期货公司外,市面上大量第三方交易...
铂银掘金APP无资质的违规平台...   铂银掘金等平台的投资者,往往是被“注册送现金”“充值返现券”“首单免亏”等广告话术吸引,进而下载...
八方淘金APP订购交易不合规,...   “八方淘金APP”“铂银掘金APP”“铂银壹号APP”等软件被指以“现货订购”为名,实际采用高杠...
在指尖订购APP订购商品亏损被...   指尖订购APP这类平台,表面是“订购交易”,实则是披着电商外衣的非法期货陷阱。绝大多数投资者被蒙...
在犀贝易购APP做商品订购交易...   市面上打着“现货投资”“贵金属交易”旗号的APP并不少,但真正合规、受监管的平台并不多。犀贝易购...
易达淘金APP虚假商品订购交易...   易达淘金APP存在严重的虚假宣传与违规交易行为。该平台打着“商品订购”的旗号,实则通过不合规的交...
大浪淘金APP白银订购亏损被骗...   大浪淘金APP最隐蔽的套路,在于其完全封闭的内盘交易系统。表面上,它宣称与国际贵金属市场接轨;实...
一品好购APP上订购白银出现亏...   一品好购APP原名“一品订购”,运营方为上海宝智未来信息技术有限公司。近期不少投资者反映在该平台...
九州订购APP贵金属订购投资骗...   九州订购APP正通过抖.音、快手、今日头条等平台大量投放投资广告,用“5元起投”“充值返现”“0...
坚锅淘金APP交易软件并不正规...   当前,市面上大量所谓的“现货商城订购”交易软件,早已偏离了正常的实物商品买卖,演变为高杠杆、高手...
斗金订购APP贵金属期货交易骗...   斗金订购APP的投资者往往被铺天盖地的广告宣传所诱导——注册即送现金、充值返现券等看似诱人的福利...
警惕!云启购APP违规经营,披...   "5元起投、充值返现、稳赚不赔"——这些诱人的广告语背后,可能是一个精心设计的金融陷阱。  近期...
量子淘金APP贵金属投资不合规...   "4元起投""充值返券""月入过万"——这些极具诱惑力的广告语在短视频平台、社交软件上铺天盖地。...
鑫汇智投APP贵金属商品订购骗...   鑫汇智投APP非法期货投资骗局,受害者在投资过程中根本不懂交易,也不去研究和验证这个平台是否正规...
矅光智策APP平台违规经营非法...   矅光智策APP对外宣称是“商城订购”“现货交易”,但查询其经营范围,并未显示具备开展现货期货交易...
黄金珠宝怎么选?内侧刻字都代表... 潮新闻客户端 记者 马焱 通讯员 任倩影 9月8日下午,“云游杭州 乐购金秋”——“浙城·浙放心”活...
原创 冰... 最近全球国债市场正在上演魔幻一幕: 美债、日债、欧债遭遇猛烈抛售,收益率冲到几十年新高,美国财政部都...
日韩股市开盘表现分化 上证报中国证券网讯 9月9日,日韩股市开盘表现分化,韩国综合指数开盘上涨0.26%,报6972.87...