鏈表中環的入口節點

qpal 發布于2019-08-16 18:28 / 742人閱讀

摘要：題目描述給一個鏈表，若其中包含環，請找出該鏈表的環的入口結點，否則，輸出。

題目描述

給一個鏈表，若其中包含環，請找出該鏈表的環的入口結點，否則，輸出null。

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead){
        
    }
}

解法一

遍歷鏈表的時候，用一個容器list依次裝入鏈表的節點，如果發現有重復的節點，那么就是鏈表的環的入口節點

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;
    }
}

時間復雜度：O(n^2)

解法二

采用雙指針的方法（這個方法還可以用來判斷鏈表中有沒有環），一個快指針一個慢指針，快指針一次走兩步，慢指針一次走一步，如果鏈表中有環，那么兩個指針一定就可以相遇，并且相遇的地方，一定在環的某處

設相遇的地方距環的入口點一邊有a個節點，一邊有b個節點，鏈表除環以外有x個節點，環中一共有c個節點（c=a+b）

那么可以得到如下關系式，用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;
    }

該方法的時間復雜度為O(n)

參考

《劍指offer》——鏈表中環的入口結點

云服務器 GPU云服務器 c語言鏈表加節點中環 linux鏈表的安全訪問小程序的入口

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/75158.html

寫一段代碼判斷單向鏈表中有沒有形成環，如果形成環，請找出環的入口處，即P點

摘要：由于要比移動的快，如果有環，一定會先進入環，而后進入環。現在問題就簡單了，由于移動的距離永遠是的一般，因此當遍歷玩整個環長度個節點的時候正好遍歷了個節點，也就是說，此時正好指向距離最遠的點。首先，關于單鏈表中的環，一般涉及到以下問題： 1.給一個單鏈表，判斷其中是否有環的存在； 2.如果存在環，找出環的入口點； 3.如果存在環，求出環上節點的個數； 4.如果存在環，求出鏈表的長度； ...

OldPanda 2019-07-01 13:56 評論0 收藏0
leetcode 鏈表相關題目解析

摘要：同時保有當前鏈表的尾部的指針以及頭部的節點指針。鏈表可能只有部分成環這意味著。頭部的引用尾部的引用始終指向尾部忽略虛假的頭部鏈表相加原題地址。生成虛假的頭部后兩個鏈表兩兩相加注意進位以及保留位即可。鏈表是沒有發生改變的。 showImg(https://segmentfault.com/img/remote/1460000018562166?w=1069&h=600); 前言本文基于...

harriszh 2019-08-26 13:38 評論0 收藏0