Java之單鏈表問(wèn)題的示例分析

這篇文章給大家分享的是有關(guān)Java之單鏈表問(wèn)題的示例分析的內(nèi)容。小編覺(jué)得挺實(shí)用的，因此分享給大家做個(gè)參考，一起跟隨小編過(guò)來(lái)看看吧。

單鏈表

單鏈表是一種鏈?zhǔn)酱嫒〉臄?shù)據(jù)結(jié)構(gòu),用一組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素。

鏈表中的數(shù)據(jù)是以結(jié)點(diǎn)來(lái)表示的，每個(gè)結(jié)點(diǎn)的構(gòu)成:元素(數(shù)據(jù)元素的映象) + 指針(指示后繼元素存儲(chǔ)位置)，元素就是存儲(chǔ)數(shù)據(jù)的存儲(chǔ)單元，指針就是連接每個(gè)結(jié)點(diǎn)的地址數(shù)據(jù)。

問(wèn)題

問(wèn)題1：給定一個(gè)單鏈表，判斷鏈表中是否有環(huán)

問(wèn)題2：給定一個(gè)鏈表，返回鏈表開(kāi)始入環(huán)的第一個(gè)節(jié)點(diǎn)，如果無(wú)環(huán)，則返回null

class Node{
    public int data;
    Node next;
    public Node(int data){
        this.data=data;
        this.next=null;
    }
}
public class linkedList {
    /*給定一個(gè)鏈表，判斷鏈表中是否有環(huán)
    思路： 如果鏈表有環(huán)的話，定義兩個(gè)節(jié)點(diǎn)fast,slow。讓fast一次走兩步，slow一次走一步；
    如果能相交，即fast=slow，說(shuō)明有交點(diǎn)，且如果有環(huán)，節(jié)點(diǎn)的next也不會(huì)為空
     */
    public Node head;
    public boolean hasCycle(){
        Node fast=this.head;
        Node slow=this.head;
        while (fast!=null&&fast.next!=null){//如果把fast.next寫(xiě)下前面，一旦fast為空，則會(huì)空指針異常
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                return true;
            }
        }
        return false;
    }
    
    //給定一個(gè)鏈表，返回鏈表開(kāi)始入環(huán)的第一個(gè)節(jié)點(diǎn)，如果無(wú)環(huán)，則返回null
    public Node detectCycle(){
        /*定義fast與slow,fast前進(jìn)2格，slow前進(jìn)一格，如果有交點(diǎn)的話，fast與slow第一次相遇時(shí)，fast的路程為slow的2倍，
        如設(shè)從頭節(jié)點(diǎn)到入環(huán)節(jié)點(diǎn)的距離為X，令入環(huán)節(jié)點(diǎn)到fast,slow第一次相遇距離為Y，環(huán)的總長(zhǎng)度為C的話;可得公式：2（X+Y）=X+Y+NC；
        得X=NC-Y，令N等于1，X=C-Y;此時(shí)讓slow從頭節(jié)點(diǎn)開(kāi)始走，當(dāng)于速度相同的fast相遇時(shí)，則為入環(huán)的節(jié)點(diǎn)。
        */
        Node fast=this.head;
        Node slow=this.head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){//第一次相遇  
                break;
            }
        }
        if(fast==null&&fast.next==null){
            return null;
        }
        //此時(shí)讓slow從頭節(jié)點(diǎn)開(kāi)始，與fast以相同速度前進(jìn)，遇到則為入環(huán)的第一個(gè)節(jié)點(diǎn)
        slow=this.head;
        while (fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }
}

感謝各位的閱讀！關(guān)于“Java之單鏈表問(wèn)題的示例分析”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，讓大家可以學(xué)到更多知識(shí)，如果覺(jué)得文章不錯(cuò)，可以把它分享出去讓更多的人看到吧！