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