新星計劃Day6【資料結構與算法】連結清單Part2

👩‍💻部落格首頁：京與舊鋪的部落格首頁

✨歡迎關注🖱點贊🎀收藏⭐留言✒

🔮本文由京與舊鋪原創

😘系列專欄：java學習

💻首發時間：🎞2022年4月30日🎠

🎨你做三四月的事，八九月就會有答案，一起加油吧

🀄如果覺得部落客的文章還不錯的話，請三連支援一下部落客哦

🎧最後的話，作者是一個新人，在很多方面還做的不好，歡迎大佬指正，一起學習哦，沖沖沖

💬推薦一款模拟面試、刷題神器👉點選進入網站

🛒導航小助手🎪

文章目錄

新星計劃Day6【資料結構與算法】連結清單Part2
🛒導航小助手🎪

@[toc]

🏳‍🌈021 單連結清單新浪面試題
💺022 單連結清單騰訊面試題
🚌023 單連結清單百度面試題
🌍024 雙向連結清單增删改查分析圖解
🦽025 雙向連結清單增删改查代碼實作
🚡026 雙向連結清單功能測試和小結
🚞027 環形連結清單介紹和約瑟夫問題
🚂028 約瑟夫問題分析圖解和實作（1）
💌029 約瑟夫問題分析圖解和實作（2）

🏳‍🌈021 單連結清單新浪面試題

查找單連結清單中的倒數第k個節點（新浪面試題）

思路

1.編寫一個方法，接收head節點，同時接收一個index

2.index表示是倒數第index個節點

3.先把連結清單從頭到尾周遊一下，得到這個連結清單的總的長度getLength

4.得到size後，我們從連結清單的第一個開始周遊（size-index）個，就可以得到了

5.如果找到了，則傳回該節點，否則傳回null

public static HeroNode findLastIndexNode(HeroNode head,int index){
    //判斷如果連結清單為空，傳回null
    if(head.next==null){
        return null;//沒有找到
    }
    //第一次周遊得到連結清單的長度（節點個數）
    int size=getLength(head);
    //第二次周遊size-index位置，就是我們倒數的第K個節點
    //先做一個index的校驗
    if(index<=0||index>size){
        return null;
    }
    //定義一個輔助變量,for循環定位到倒數的index
    HeroNode cur=head.next;
    for(int i=0;i<size-index;i++){
        cur=cur.next;
    }
    return cur;
}

💺022 單連結清單騰訊面試題

将單連結清單進行反轉

思路：1.先定義一個節點reverseHead=new HeroNode();

2.從頭到尾周遊原來的連結清單，每周遊一個節點，就将其取出，并放在新的連結清單的最前端

3.原來的連結清單的head.next=reverseHead.next

public static void reverseList(HeroNode head){
    //如果目前連結清單為空，或者隻有一個節點，無需反轉，直接傳回
    if(head.next==null||head.next.next==null){
        return;
    }
    //定義一個輔助的指針（變量），幫助我們周遊原來的連結清單
    HeroNode cur=head.next;
    HeroNode next=null;//指向目前節點【cur】的下一個節點
    HeroNode reverseHead=new HeroNode(0,"","");
    //從頭到尾周遊原來的連結清單，每周遊一個節點，就将其取出，并放在新的連結清單的最前端
    //動腦筋
    while(cur!=null){
        next=cur.next;//先暫時儲存目前節點的下一個節點，因為後面需要使用
        cur.next=reverseHead.next;//将cur的下一個節點指向新的連結清單的頭節點
        reverseHead.next=cur;//将cur連接配接到新的連結清單
        cur=next;//讓cur後移
    }
    //将head.next指向reverseHead.next，實作單連結清單的反轉
    head.next=reverseHead.next;
}

🚌023 單連結清單百度面試題

從尾到頭列印單連結清單

思路：

1.上面的題的要求就是逆序列印單連結清單

2.方式一：先将單連結清單進行一個反轉操作，然後再周遊即可，這樣做的問題是會破壞原來的單連結清單的結構，不建議這樣做

3.方式二：可以利用棧這個資料結構，将各個節點壓入到棧中，利用棧的先進後出的特點就實作了這個逆序列印的效果

舉例示範棧的使用

import java.util.Stack;
public class TestStack{
    public static void main(String[] args){
        Stack<String> stack=new Stack();
        //入棧
        stack.add("jack");
        stack.add("tom");
        stack.add("smith");
        //出棧
        //smith,tom,jack
        while(stack.size()>0){
            System.out.println(stack.pop());//pop就是将棧頂的資料取出
        }
    }
}

方式二：可以利用棧這個資料結構，将各個節點壓入到棧中，利用棧的先進後出的特點就實作了這個逆序列印的效果

public static void reversePrint(HeroNode head){
    if(head.next==null){
        return;//空連結清單，不能列印
    }
    //建立要給一個棧，将各個節點壓入棧
    Stack<HeroNode> stack=new Stack<HeroNode>();
    HeroNode cur=head.next;
    //将連結清單的所有節點壓入棧中
    while(cur!=null){
        stack.push(cur);
        cur=cur.next;//cur後移，這樣就可以壓入下一個節點
    }
    //将棧中的節點進行列印，pop出棧
    while(stack.size()>0){
        System.out.println(stack.pop());//stack的特點是先進後出
    }
}

🌍024 雙向連結清單增删改查分析圖解

單連結清單的缺點

1.單向連結清單的查詢節點隻能是一個方向

2.單向連結清單不能實作自我删除，隻能通過找到前一個節點來删除

雙向連結清單分析

pre：指向前一個節點

分析雙向連結清單的周遊，添加，修改，删除的操作思路—代碼實作

1）周遊的方式和單連結清單一樣，隻是可以向前查找，也可以向後查找

2）添加（預設添加到雙向連結清單的最後）

（1）先找到雙向連結清單的最後這個節點

（2）temp.next=newHeroNode

(3)newHeroNode.pre=temp;

(4)修改思路和原來的單向連結清單一樣

（5）删除

（1）因為是雙向連結清單，是以，我們可以實作自我删除某個節點

（2）直接找到要删除的這個節點，比如temp

（3）temp.pre.next=temp.next

(4)temp.next.pre=temp.pre;

🦽025 雙向連結清單增删改查代碼實作

//建立一個雙向連結清單的類
class DoubleLinkedList{
    //先初始化一個頭節點，頭節點不要動,不存放具體的資料
    private HreoNode2 head=new HeroNode2(0,"","");
    //傳回頭節點
    public HeroNode2 getHead(){
        return head;
    }
    //周遊雙向連結清單的方法
    //顯示連結清單【周遊】
    public void list(){
        //判斷連結清單是否為空
        if(head.next==null){
            System.out.println("連結清單為空");
            return;
        }
        //因為頭節點，不能動，是以我們需要一個輔助變量來周遊
        HeroNode temp=head.next;
        while(true){
            //判斷是否到連結清單最後
            if(temp==null){
                break;
            }
            //輸出節點的資訊
            System.out.println(temp);
            //将temp後移，一定小心
            temp=temp.next;
        }
    }
    //添加一個節點到雙向連結清單的最後
    public void add(HeroNode2 heroNode){
        //因為head節點不能動，是以我們需要一個輔助周遊temp
        HeroNode2 temp=head;
        //周遊連結清單，找到最後
        while(true){
            if(temp.next==null){
                break;
            }
            //如果沒有找到最後，将temp後移
            temp=temp.next;
        }
        //當退出while循環時，temp就指向了連結清單的最後
        //形成一個雙向連結清單
        temp.next=heroNode;
        heroNode.pre=temp;
    }
    //修改一個節點的内容，可以看到雙向連結清單的節點内容修改和單向連結清單一樣
    //隻是節點的類型改成了HeroNode2
    public void update(HeroNode2 newHeroNode){
        //判斷是否為空
        if(head.next==null){
            System.out.println("連結清單為空");
            return;
        }
        //找到需要修改的節點，根據no編寫
        //定義一個輔助變量
        HeroNode2 temp=head.next();
        boolean flag=false;//表示是否找到節點
        while(true){
            if(temp==null){//已經周遊完連結清單
                break;
            }
            if(temp.no==newHeroNode.no){
                //找到
                flag=true;
                break;
            }
            temp=temp.next;
        }
        //根據flag判斷是否找到要修改的節點
        if(flag){
            temp.name=newHreoNode.name;
             temp.nickname=newHreoNode.nickname;
        }else{//沒有找到
             System.out.printt("沒有找到編号%d的節點，不能修改\n",newHeroNode.no);
        }
    }
    //從雙向連結清單中删除一個節點
    //1.對于雙向連結清單，我們可以直接找到要删除的這個節點
    //2.找到後，自我删除即可
    public void del(int no){
        //判斷目前連結清單是否為空
        if(head.next==null){//空連結清單
            System.out.println("連結清單為空，無法删除");
            return;
        }
        HeroNode2 temp=head.next;//輔助變量（指針）
        boolean flag=false;//标志是否找到待删除節點的
        while(true){
            if(temp==null){//已經到連結清單的最後
                break;
            }
            if(temp.no==no){
                //找到了待删除節點的前一個節點temp
                flag=true;
                break;
            }
            temp=temp.next;//temp後移，周遊
        }
        //判斷flag
        if(flag){//找到
            //可以删除
            temp.pre.next=temp.next;
            //這裡我們的代碼有問題  
            //如果是最後一個節點，就不需要執行下面這句話，否則會出現空指針異常
            if(temp.next!=null){
                temp.next.pre=temp.pre;
            }
            
        }else{
            System.out.printf("要删除的%d節點不存在\n",no);
        }
    }
}
//定義HeroNode2,每個HeroNode對象就是一個節點
class HeroNode2{
    public int no;
    public String name;
    public String nickname;
    public HeroNode next;//執行下一個節點，預設為null
    public HeroNode pre;//指向前一個節點，預設為null
    //構造器
    public HeroNode(int hNo,String name,String nickname){
        this.no=no;
        this.name=name;
        this.nickname=nickname;
    }
    //為了顯示友善，我們重寫一下toString
    @Override
    public String toString(){
        return "HeroNode [no="+no+",name="+name+",nickname="+nickname+"]";
    }
    
}

🚡026 雙向連結清單功能測試和小結

public class DoubleLinkedListDemo{
    public static void main(String[] args){
        //測試
        System.out.println("雙向連結清單的測試");
        //先建立節點
        HeroNode2 her1 = new HeroNode2(1, "宋江", "及時雨");
        HeroNode2 her2 = new HeroNode2(2, "盧俊義", "玉麒麟");
        HeroNode2 her3 = new HeroNode2(3, "吳用", "智多星");
        HeroNode2 her4 = new HeroNode2(4, "林沖", "豹子頭");
        //建立一個雙向連結清單
        DoubleLinkedList doubleLinkedList=new DoubleLinkedList;
        doubleLinkedList.add(hero1);
        doubleLinkedList.add(hero2);
        doubleLinkedList.add(hero3);
        doubleLinkedList.add(hero4);
        
        doubleLinkedList.list();
        //修改
        HeroNode2 newHeroNode = new HeroNode2(4, "公孫勝", "入雲龍");
        doubleLinkedList.update(newHeroNode);
        System.out.println("修改後的連結清單情況");
        doubleLinkedList.list();
        //删除
        doubleLinkedList.del(3);
        System.out.println("删除後的連結清單情況");
        doubleLinkedList.list();
    }
}

🚞027 環形連結清單介紹和約瑟夫問題

Josephu(約瑟夫、約瑟夫環) 問題 Josephu 問題為：設編号為 1，2，… n 的 n 個人圍坐一圈，約定編号為 k（1<=k<=n）的人從 1 開始報數，數到 m 的那個人出列，它的下一位又從 1 開始報數，數到 m 的那個人又出列，依次類推，直到所有人出列為止，由此産生一個出隊編号的序列。

提示：用一個不帶頭結點的循環連結清單來處理 Josephu 問題：先構成一個有 n 個結點的單循環連結清單，然後由 k 結點起從 1 開始計數，計到 m 時，對應結點從連結清單中删除，然後再從被删除結點的下一個結點又從 1 開始計數，直到最後一個結點從連結清單中删除算法結束

🚂028 約瑟夫問題分析圖解和實作（1）

建構一個單向的環形連結清單思路

1.先建立第一個節點，讓first指向該節點，并形成環形

2.後面當我們每建立一個新的節點，就把該節點，加入到已有的環形連結清單中即可

周遊環形連結清單

1.先讓一個輔助指針（變量）指向first節點

2.然後通過一個while循環周遊該環形連結清單即可 cueBoy.next==first結束

public class Josepfu{
    public static void main(String[] args){
        //測試一把看看建構環形連結清單，和周遊是否ok
        CircleSingleLinkedList circleSingleLinkedList=new CircleSingleLinkedList;
        circleSingleLinkedList.addBoy(5);//加入五個小孩節點
        circleSingleLinkedList.showBoy();
    }
}
//建立一個環形的單向連結清單
class CircleSingleLinkedList{
    //建立一個first節點，目前沒有編号
    private Boy first=new Boy(-1);
    //添加小孩的節點，建構成一個環形連結清單
    public void addBoy(int nums){
        //nums做一個資料校驗
        if(nums<1){
            System.out.println("nums的值不正确");
            return;
        }
        Boy curBoy=null;//輔助指針，幫助建構環形連結清單
        //使用for循環來建立我們的環形連結清單
        for(int i=1;i<=nums;i++){
            //根據編号建立小孩節點
            Boy boy=new Boy(i);
            //如果是第一個小孩
            if(i==1){
                first=boy;
                first.setNext(first);//構成環
                curBoy=first;//讓curBoy指向第一個小孩
            }else{
                curBoy.setNext(boy);//
                boy.setNext(first);//
                curBoy=boy;
            }
        }
    }
    //周遊目前環形連結清單
    public void showBoy(){
        //判斷連結清單是否為空
        if(first==null){
            System.out.println("沒有任何小孩");
            return;
        }
        //因為first不能動，是以我們仍然使用一個輔助指針完成周遊
        Boy curBoy=first;
        while(true){
            System.out.printf("小孩的編号%d \n",curBoy.getNo());
            if(curBoy.getNext()==first){//說明已經周遊完畢
                break;
            }
            curBoy=curBoy.getNext();//curBoy後移
        }
    }
}
//建立一個Boy類，表示一個節點
class Boy{
    private int no;//編号
    private Boy next;//指向下一個節點，預設null
    public Boy(int no){
        this.no=no;
    }
    public int getNo(){
        return no;
    }
    public void setNo(int  no){
        this.no=no;
    }
    public Boy getNext(){
        return next;
    }
    public void setNext(Boy next){
        this.next=next;
    }
}

💌029 約瑟夫問題分析圖解和實作（2）

根據使用者的輸入，生成一個小孩出圈的順序

n=5，即有5個人

k=1，從第一個人開始報數

m=2，數2下

1.需要建立一個輔助指針（變量）helper，事先應該指向環形連結清單的最後這個節點

補充：

小孩報數前，先讓first和helper移動k-1次

2.當小孩報數時，讓first和helper這個指針同時的移動m-1次

3.這時都可以将first指向的小孩節點出圈

first=first.next

helper.next=first;

原來first指向的節點就沒有任何引用了，就會被回收

//startNo  表示從第幾個小孩開始數數
//countNum  表示數幾下
//nums 表示最初有多少小孩在圈中
public void countBoy(int startNo,int countNum,int nums){
    //先對資料進行校驗
    if(first==null||starNo<1||startNo>nums){
        System.out.println("參數輸入有誤，請重新輸入");
        return;
    }
    //建立要給輔助指針，幫助完成小孩出圈
    Boy helper=first;
    //需要建立一個輔助指針（變量）helper，事先應該指向環形連結清單的最後這個節點
    while(true){
        if(helper.getNext()==first){//說明helper指向最後小孩節點
            break;
        }
        helper=helper.getNext();
    }
    //小孩報數前，先讓first和helper移動k-1次
    for(int j=0;j<startNo-1;j++){
        first=first.getNext();
        helper=helper.getNext();
    }
    //當小孩報數時，讓first和helper這個指針同時的移動m-1次,然後出圈
    //這裡是一個循環操作，直到圈中隻有一個節點
    while(true){
        if(helper==first){  //說明圈中隻有一個節點
            break;
        }
        //讓first和helper指針同時移動countnum-1次
        for(int j=0;j<countNum-1;j++){
            first=first.getNext();
        helper=helper.getNext();
        }
        //這時first指向的節點，就是要出圈的小孩節點
        first=first.getNext();
        helper.setNext(first);
        
    }
    System.out.printf("最後留在圈中的小孩編号為%d\n",first.getNo());
}

下期預告：力扣每日一練之數組中篇Day2

新星計劃Day6【資料結構與算法】連結清單Part2