資訊專(zhuān)欄INFORMATION COLUMN
摘要：題目描述給一個(gè)鏈表，若其中包含環(huán)，請(qǐng)找出該鏈表的環(huán)的入口結(jié)點(diǎn)，否則，輸出。
題目描述
給一個(gè)鏈表，若其中包含環(huán)，請(qǐng)找出該鏈表的環(huán)的入口結(jié)點(diǎn)，否則，輸出null。
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead){
}
}
解法一
遍歷鏈表的時(shí)候，用一個(gè)容器list依次裝入鏈表的節(jié)點(diǎn)，如果發(fā)現(xiàn)有重復(fù)的節(jié)點(diǎn)，那么就是鏈表的環(huán)的入口節(jié)點(diǎn)
import java.util.ArrayList;
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead){
ArrayList list = new ArrayList<>();
while (!list.contains(pHead) && pHead != null){
list.add(pHead);
pHead = pHead.next;
}
return pHead;
}
}
時(shí)間復(fù)雜度：O(n^2)
解法二采用雙指針的方法（這個(gè)方法還可以用來(lái)判斷鏈表中有沒(méi)有環(huán)），一個(gè)快指針一個(gè)慢指針，快指針一次走兩步，慢指針一次走一步，如果鏈表中有環(huán)，那么兩個(gè)指針一定就可以相遇，并且相遇的地方，一定在環(huán)的某處
設(shè)相遇的地方距環(huán)的入口點(diǎn)一邊有a個(gè)節(jié)點(diǎn)，一邊有b個(gè)節(jié)點(diǎn)，鏈表除環(huán)以外有x個(gè)節(jié)點(diǎn)，環(huán)中一共有c個(gè)節(jié)點(diǎn)（c=a+b）
那么可以得到如下關(guān)系式，用b = c -a表示
][1]
public ListNode EntryNodeOfLoop(ListNode pHead){
if(pHead == null || pHead.next == null)return null;
ListNode slow = pHead.next;
ListNode fast = pHead.next.next;
while (slow != fast && pHead != null){
slow = slow.next;
fast = fast.next.next;
}
slow = pHead;
while(slow != fast){
slow = slow.next;
fast = fast.next;
}
return slow;
}
該方法的時(shí)間復(fù)雜度為O(n)
參考《劍指offer》——鏈表中環(huán)的入口結(jié)點(diǎn)
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/75158.html
摘要：由于要比移動(dòng)的快，如果有環(huán)，一定會(huì)先進(jìn)入環(huán)，而后進(jìn)入環(huán)。現(xiàn)在問(wèn)題就簡(jiǎn)單了，由于移動(dòng)的距離永遠(yuǎn)是的一般，因此當(dāng)遍歷玩整個(gè)環(huán)長(zhǎng)度個(gè)節(jié)點(diǎn)的時(shí)候正好遍歷了個(gè)節(jié)點(diǎn)，也就是說(shuō)，此時(shí)正好指向距離最遠(yuǎn)的點(diǎn)。 首先，關(guān)于單鏈表中的環(huán)，一般涉及到以下問(wèn)題： 1.給一個(gè)單鏈表，判斷其中是否有環(huán)的存在； 2.如果存在環(huán)，找出環(huán)的入口點(diǎn)； 3.如果存在環(huán)，求出環(huán)上節(jié)點(diǎn)的個(gè)數(shù)； 4.如果存在環(huán)，求出鏈表的長(zhǎng)度； ...
摘要：同時(shí)保有當(dāng)前鏈表的尾部的指針以及頭部的節(jié)點(diǎn)指針。鏈表可能只有部分成環(huán)這意味著。頭部的引用尾部的引用始終指向尾部忽略虛假的頭部鏈表相加原題地址。生成虛假的頭部后兩個(gè)鏈表兩兩相加注意進(jìn)位以及保留位即可。鏈表是沒(méi)有發(fā)生改變的。 showImg(https://segmentfault.com/img/remote/1460000018562166?w=1069&h=600); 前言 本文基于...
閱讀 2938·2023-04-26 02:22
閱讀 2292·2021-11-17 09:33
閱讀 3144·2021-09-22 16:06
閱讀 1078·2021-09-22 15:54
閱讀 3541·2019-08-29 13:44
閱讀 1921·2019-08-29 12:37
閱讀 1327·2019-08-26 14:04
閱讀 1920·2019-08-26 11:57
