劍指 Offer II 022. 鏈表中環(huán)的入口節(jié)點
點擊上方“JavaEdge”，關(guān)注公眾號
解析
先通過快慢指針判斷有無環(huán)
無環(huán)
直接返回null
有環(huán)
假設(shè)：
起點到環(huán)起點的距離是a
環(huán)的長度是k
且此時A、B在距離環(huán)起點x距離處相遇
即慢指針再走x步就到達(dá)環(huán)的入口，此時slow走過的距離
a + nk + (k - x)快指針走過的距離：
a + mk + (k - x)由快慢的定義可知：
a + mk + (k - x) = 2 * (a + nk + (k - x))
化簡得：
a = (m - 2n -1)k + x
可知a為k的整數(shù)倍加x，而AB相遇的位置再走x步恰是環(huán)入口，所以此時讓其中一個指針指向起點，然后同步走，一定能在環(huán)入口相遇！
所以可得代碼：
package com.javaedge;/*** @author JavaEdge* @date 2021/8/17*/public class DetectCycle {static class ListNode {int val;ListNode next;ListNode(int x) {val = x;next = null;}}public ListNode detectCycle(ListNode head) {ListNode slow = head;ListNode fast = head;boolean isCircled = false;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) {isCircled = true;break;}}if (!isCircled) {// 無環(huán)return null;}slow = head;while (slow != fast) {slow = slow.next;fast = fast.next;}return slow;}}
往期推薦
目前交流群已有 800+人，旨在促進(jìn)技術(shù)交流，可關(guān)注公眾號添加筆者微信邀請進(jìn)群
喜歡文章，點個“在看、點贊、分享”素質(zhì)三連支持一下~
評論
圖片
表情