新星計(jì)劃Day6【數(shù)據(jù)結(jié)構(gòu)與算法】 鏈表Part2

?????博客主頁：京與舊鋪的博客主頁

?歡迎關(guān)注??點(diǎn)贊??收藏?留言?

??本文由京與舊鋪原創(chuàng)，csdn首發(fā)！

??系列專欄：java學(xué)習(xí)

??首發(fā)時(shí)間：??2022年4月30日??

??你做三四月的事，八九月就會(huì)有答案，一起加油吧

??如果覺得博主的文章還不錯(cuò)的話，請三連支持一下博主哦

??最后的話，作者是一個(gè)新人，在很多方面還做的不好，歡迎大佬指正，一起學(xué)習(xí)哦，沖沖沖
??推薦一款模擬面試、刷題神器??點(diǎn)擊進(jìn)入網(wǎng)站

??導(dǎo)航小助手??

?????021 單鏈表新浪面試題

查找單鏈表中的倒數(shù)第k個(gè)節(jié)點(diǎn)（新浪面試題）

思路

1.編寫一個(gè)方法，接收head節(jié)點(diǎn)，同時(shí)接收一個(gè)index

2.index表示是倒數(shù)第index個(gè)節(jié)點(diǎn)

3.先把鏈表從頭到尾遍歷一下，得到這個(gè)鏈表的總的長度getLength

4.得到size后，我們從鏈表的第一個(gè)開始遍歷（size-index）個(gè)，就可以得到了

5.如果找到了，則返回該節(jié)點(diǎn)，否則返回null

public static HeroNode findLastIndexNode(HeroNode head,int index){
    //判斷如果鏈表為空，返回null
    if(head.next==null){
        return null;//沒有找到
    }
    //第一次遍歷得到鏈表的長度（節(jié)點(diǎn)個(gè)數(shù)）
    int size=getLength(head);
    //第二次遍歷size-index位置，就是我們倒數(shù)的第K個(gè)節(jié)點(diǎn)
    //先做一個(gè)index的校驗(yàn)
    if(index<=0||index>size){
        return null;
    }
    //定義一個(gè)輔助變量,for循環(huán)定位到倒數(shù)的index
    HeroNode cur=head.next;
    for(int i=0;i<size-index;i++){
        cur=cur.next;
    }
    return cur;
}

??022 單鏈表騰訊面試題

將單鏈表進(jìn)行反轉(zhuǎn)

思路：1.先定義一個(gè)節(jié)點(diǎn)reverseHead=new HeroNode();

2.從頭到尾遍歷原來的鏈表，每遍歷一個(gè)節(jié)點(diǎn)，就將其取出，并放在新的鏈表的最前端

3.原來的鏈表的head.next=reverseHead.next

public static void reverseList(HeroNode head){
    //如果當(dāng)前鏈表為空，或者只有一個(gè)節(jié)點(diǎn)，無需反轉(zhuǎn)，直接返回
    if(head.next==null||head.next.next==null){
        return;
    }
    //定義一個(gè)輔助的指針（變量），幫助我們遍歷原來的鏈表
    HeroNode cur=head.next;
    HeroNode next=null;//指向當(dāng)前節(jié)點(diǎn)【cur】的下一個(gè)節(jié)點(diǎn)
    HeroNode reverseHead=new HeroNode(0,"","");
    //從頭到尾遍歷原來的鏈表，每遍歷一個(gè)節(jié)點(diǎn)，就將其取出，并放在新的鏈表的最前端
    //動(dòng)腦筋
    while(cur!=null){
        next=cur.next;//先暫時(shí)保存當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，因?yàn)楹竺嫘枰褂?/span>
        cur.next=reverseHead.next;//將cur的下一個(gè)節(jié)點(diǎn)指向新的鏈表的頭節(jié)點(diǎn)
        reverseHead.next=cur;//將cur連接到新的鏈表
        cur=next;//讓cur后移
    }
    //將head.next指向reverseHead.next，實(shí)現(xiàn)單鏈表的反轉(zhuǎn)
    head.next=reverseHead.next;
}

??023 單鏈表百度面試題

從尾到頭打印單鏈表

思路：

1.上面的題的要求就是逆序打印單鏈表

2.方式一：先將單鏈表進(jìn)行一個(gè)反轉(zhuǎn)操作，然后再遍歷即可，這樣做的問題是會(huì)破壞原來的單鏈表的結(jié)構(gòu)，不建議這樣做

3.方式二：可以利用棧這個(gè)數(shù)據(jù)結(jié)構(gòu)，將各個(gè)節(jié)點(diǎn)壓入到棧中，利用棧的先進(jìn)后出的特點(diǎn)就實(shí)現(xiàn)了這個(gè)逆序打印的效果

舉例演示棧的使用

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就是將棧頂?shù)臄?shù)據(jù)取出
        }
    }
}

方式二：可以利用棧這個(gè)數(shù)據(jù)結(jié)構(gòu)，將各個(gè)節(jié)點(diǎn)壓入到棧中，利用棧的先進(jìn)后出的特點(diǎn)就實(shí)現(xiàn)了這個(gè)逆序打印的效果

public static void reversePrint(HeroNode head){
    if(head.next==null){
        return;//空鏈表，不能打印
    }
    //創(chuàng)建要給一個(gè)棧，將各個(gè)節(jié)點(diǎn)壓入棧
    Stack<HeroNode> stack=new Stack<HeroNode>();
    HeroNode cur=head.next;
    //將鏈表的所有節(jié)點(diǎn)壓入棧中
    while(cur!=null){
        stack.push(cur);
        cur=cur.next;//cur后移，這樣就可以壓入下一個(gè)節(jié)點(diǎn)
    }
    //將棧中的節(jié)點(diǎn)進(jìn)行打印，pop出棧
    while(stack.size()>0){
        System.out.println(stack.pop());//stack的特點(diǎn)是先進(jìn)后出
    }
}

??024 雙向鏈表增刪改查分析圖解

單鏈表的缺點(diǎn)

1.單向鏈表的查詢節(jié)點(diǎn)只能是一個(gè)方向

2.單向鏈表不能實(shí)現(xiàn)自我刪除，只能通過找到前一個(gè)節(jié)點(diǎn)來刪除

雙向鏈表分析

pre：指向前一個(gè)節(jié)點(diǎn)

分析雙向鏈表的遍歷，添加，修改，刪除的操作思路—代碼實(shí)現(xiàn)

1）遍歷的方式和單鏈表一樣，只是可以向前查找，也可以向后查找

2）添加（默認(rèn)添加到雙向鏈表的最后）

（1）先找到雙向鏈表的最后這個(gè)節(jié)點(diǎn)

? （2）temp.next=newHeroNode

? (3)newHeroNode.pre=temp;

(4)修改思路和原來的單向鏈表一樣

（5）刪除

? （1）因?yàn)槭请p向鏈表，因此，我們可以實(shí)現(xiàn)自我刪除某個(gè)節(jié)點(diǎn)

? （2）直接找到要?jiǎng)h除的這個(gè)節(jié)點(diǎn)，比如temp

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

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

??025 雙向鏈表增刪改查代碼實(shí)現(xiàn)

//創(chuàng)建一個(gè)雙向鏈表的類
class DoubleLinkedList{
    //先初始化一個(gè)頭節(jié)點(diǎn)，頭節(jié)點(diǎn)不要?jiǎng)?不存放具體的數(shù)據(jù)
    private HreoNode2 head=new HeroNode2(0,"","");
    //返回頭節(jié)點(diǎn)
    public HeroNode2 getHead(){
        return head;
    }
    //遍歷雙向鏈表的方法
    //顯示鏈表【遍歷】
    public void list(){
        //判斷鏈表是否為空
        if(head.next==null){
            System.out.println("鏈表為空");
            return;
        }
        //因?yàn)轭^節(jié)點(diǎn)，不能動(dòng)，因此我們需要一個(gè)輔助變量來遍歷
        HeroNode temp=head.next;
        while(true){
            //判斷是否到鏈表最后
            if(temp==null){
                break;
            }
            //輸出節(jié)點(diǎn)的信息
            System.out.println(temp);
            //將temp后移，一定小心
            temp=temp.next;
        }
    }
    //添加一個(gè)節(jié)點(diǎn)到雙向鏈表的最后
    public void add(HeroNode2 heroNode){
        //因?yàn)閔ead節(jié)點(diǎn)不能動(dòng)，因此我們需要一個(gè)輔助遍歷temp
        HeroNode2 temp=head;
        //遍歷鏈表，找到最后
        while(true){
            if(temp.next==null){
                break;
            }
            //如果沒有找到最后，將temp后移
            temp=temp.next;
        }
        //當(dāng)退出while循環(huán)時(shí)，temp就指向了鏈表的最后
        //形成一個(gè)雙向鏈表
        temp.next=heroNode;
        heroNode.pre=temp;
    }
    //修改一個(gè)節(jié)點(diǎn)的內(nèi)容，可以看到雙向鏈表的節(jié)點(diǎn)內(nèi)容修改和單向鏈表一樣
    //只是節(jié)點(diǎn)的類型改成了HeroNode2
    public void update(HeroNode2 newHeroNode){
        //判斷是否為空
        if(head.next==null){
            System.out.println("鏈表為空");
            return;
        }
        //找到需要修改的節(jié)點(diǎn)，根據(jù)no編寫
        //定義一個(gè)輔助變量
        HeroNode2 temp=head.next();
        boolean flag=false;//表示是否找到節(jié)點(diǎn)
        while(true){
            if(temp==null){//已經(jīng)遍歷完鏈表
                break;
            }
            if(temp.no==newHeroNode.no){
                //找到
                flag=true;
                break;
            }
            temp=temp.next;
        }
        //根據(jù)flag判斷是否找到要修改的節(jié)點(diǎn)
        if(flag){
            temp.name=newHreoNode.name;
             temp.nickname=newHreoNode.nickname;
        }else{//沒有找到
             System.out.printt("沒有找到編號%d的節(jié)點(diǎn)，不能修改\n",newHeroNode.no);
        }
    }
    //從雙向鏈表中刪除一個(gè)節(jié)點(diǎn)
    //1.對于雙向鏈表，我們可以直接找到要?jiǎng)h除的這個(gè)節(jié)點(diǎn)
    //2.找到后，自我刪除即可
    public void del(int no){
        //判斷當(dāng)前鏈表是否為空
        if(head.next==null){//空鏈表
            System.out.println("鏈表為空，無法刪除");
            return;
        }
        HeroNode2 temp=head.next;//輔助變量（指針）
        boolean flag=false;//標(biāo)志是否找到待刪除節(jié)點(diǎn)的
        while(true){
            if(temp==null){//已經(jīng)到鏈表的最后
                break;
            }
            if(temp.no==no){
                //找到了待刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)temp
                flag=true;
                break;
            }
            temp=temp.next;//temp后移，遍歷
        }
        //判斷flag
        if(flag){//找到
            //可以刪除
            temp.pre.next=temp.next;
            //這里我們的代碼有問題  
            //如果是最后一個(gè)節(jié)點(diǎn)，就不需要執(zhí)行下面這句話，否則會(huì)出現(xiàn)空指針異常
            if(temp.next!=null){
                temp.next.pre=temp.pre;
            }
            
        }else{
            System.out.printf("要?jiǎng)h除的%d節(jié)點(diǎn)不存在\n",no);
        }
    }
}
//定義HeroNode2,每個(gè)HeroNode對象就是一個(gè)節(jié)點(diǎn)
class HeroNode2{
    public int no;
    public String name;
    public String nickname;
    public HeroNode next;//執(zhí)行下一個(gè)節(jié)點(diǎn)，默認(rèn)為null
    public HeroNode pre;//指向前一個(gè)節(jié)點(diǎn)，默認(rèn)為null
    //構(gòu)造器
    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 雙向鏈表功能測試和小結(jié)

public class DoubleLinkedListDemo{
    public static void main(String[] args){
        //測試
        System.out.println("雙向鏈表的測試");
        //先創(chuàng)建節(jié)點(diǎn)
        HeroNode2 her1 = new HeroNode2(1, "宋江", "及時(shí)雨");
        HeroNode2 her2 = new HeroNode2(2, "盧俊義", "玉麒麟");
        HeroNode2 her3 = new HeroNode2(3, "吳用", "智多星");
        HeroNode2 her4 = new HeroNode2(4, "林沖", "豹子頭");
        //創(chuàng)建一個(gè)雙向鏈表
        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 環(huán)形鏈表介紹和約瑟夫問題

Josephu(約瑟夫、約瑟夫環(huán)) 問題 Josephu 問題為：設(shè)編號為 1，2，… n 的 n 個(gè)人圍坐一圈，約定編號為 k（1<=k<=n）的人從 1 開始報(bào)數(shù)，數(shù) 到 m 的那個(gè)人出列，它的下一位又從 1 開始報(bào)數(shù)，數(shù)到 m 的那個(gè)人又出列，依次類推，直到所有人出列為止，由 此產(chǎn)生一個(gè)出隊(duì)編號的序列。

提示：用一個(gè)不帶頭結(jié)點(diǎn)的循環(huán)鏈表來處理 Josephu 問題：先構(gòu)成一個(gè)有 n 個(gè)結(jié)點(diǎn)的單循環(huán)鏈表，然后由 k 結(jié) 點(diǎn)起從 1 開始計(jì)數(shù)，計(jì)到 m 時(shí)，對應(yīng)結(jié)點(diǎn)從鏈表中刪除，然后再從被刪除結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)又從 1 開始計(jì)數(shù)，直 到最后一個(gè)結(jié)點(diǎn)從鏈表中刪除算法結(jié)束

??028 約瑟夫問題分析圖解和實(shí)現(xiàn)（1）

構(gòu)建一個(gè)單向的環(huán)形鏈表思路

1.先創(chuàng)建第一個(gè)節(jié)點(diǎn)，讓first指向該節(jié)點(diǎn)，并形成環(huán)形

2.后面當(dāng)我們每創(chuàng)建一個(gè)新的節(jié)點(diǎn)，就把該節(jié)點(diǎn)，加入到已有的環(huán)形鏈表中即可

遍歷環(huán)形鏈表

1.先讓一個(gè)輔助指針（變量）指向first節(jié)點(diǎn)

2.然后通過一個(gè)while循環(huán)遍歷該環(huán)形鏈表即可 cueBoy.next==first結(jié)束

public class Josepfu{
    public static void main(String[] args){
        //測試一把看看構(gòu)建環(huán)形鏈表，和遍歷是否ok
        CircleSingleLinkedList circleSingleLinkedList=new CircleSingleLinkedList;
        circleSingleLinkedList.addBoy(5);//加入五個(gè)小孩節(jié)點(diǎn)
        circleSingleLinkedList.showBoy();
    }
}
//創(chuàng)建一個(gè)環(huán)形的單向鏈表
class CircleSingleLinkedList{
    //創(chuàng)建一個(gè)first節(jié)點(diǎn)，當(dāng)前沒有編號
    private Boy first=new Boy(-1);
    //添加小孩的節(jié)點(diǎn)，構(gòu)建成一個(gè)環(huán)形鏈表
    public void addBoy(int nums){
        //nums做一個(gè)數(shù)據(jù)校驗(yàn)
        if(nums<1){
            System.out.println("nums的值不正確");
            return;
        }
        Boy curBoy=null;//輔助指針，幫助構(gòu)建環(huán)形鏈表
        //使用for循環(huán)來創(chuàng)建我們的環(huán)形鏈表
        for(int i=1;i<=nums;i++){
            //根據(jù)編號創(chuàng)建小孩節(jié)點(diǎn)
            Boy boy=new Boy(i);
            //如果是第一個(gè)小孩
            if(i==1){
                first=boy;
                first.setNext(first);//構(gòu)成環(huán)
                curBoy=first;//讓curBoy指向第一個(gè)小孩
            }else{
                curBoy.setNext(boy);//
                boy.setNext(first);//
                curBoy=boy;
            }
        }
    }
    //遍歷當(dāng)前環(huán)形鏈表
    public void showBoy(){
        //判斷鏈表是否為空
        if(first==null){
            System.out.println("沒有任何小孩");
            return;
        }
        //因?yàn)閒irst不能動(dòng)，因此我們?nèi)匀皇褂靡粋€(gè)輔助指針完成遍歷
        Boy curBoy=first;
        while(true){
            System.out.printf("小孩的編號%d \n",curBoy.getNo());
            if(curBoy.getNext()==first){//說明已經(jīng)遍歷完畢
                break;
            }
            curBoy=curBoy.getNext();//curBoy后移
        }
    }
}
//創(chuàng)建一個(gè)Boy類，表示一個(gè)節(jié)點(diǎn)
class Boy{
    private int no;//編號
    private Boy next;//指向下一個(gè)節(jié)點(diǎn)，默認(rèn)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 約瑟夫問題分析圖解和實(shí)現(xiàn)（2）

根據(jù)用戶的輸入，生成一個(gè)小孩出圈的順序

n=5，即有5個(gè)人

k=1，從第一個(gè)人開始報(bào)數(shù)

m=2，數(shù)2下

1.需要?jiǎng)?chuàng)建一個(gè)輔助指針（變量）helper，事先應(yīng)該指向環(huán)形鏈表的最后這個(gè)節(jié)點(diǎn)

補(bǔ)充：

小孩報(bào)數(shù)前，先讓first和helper移動(dòng)k-1次

2.當(dāng)小孩報(bào)數(shù)時(shí)，讓first和helper這個(gè)指針同時(shí)的移動(dòng)m-1次

3.這時(shí)都可以將first指向的小孩節(jié)點(diǎn)出圈

first=first.next

helper.next=first;

原來first指向的節(jié)點(diǎn)就沒有任何引用了，就會(huì)被回收

//startNo  表示從第幾個(gè)小孩開始數(shù)數(shù)
//countNum  表示數(shù)幾下
//nums 表示最初有多少小孩在圈中
public void countBoy(int startNo,int countNum,int nums){
    //先對數(shù)據(jù)進(jìn)行校驗(yàn)
    if(first==null||starNo<1||startNo>nums){
        System.out.println("參數(shù)輸入有誤，請重新輸入");
        return;
    }
    //創(chuàng)建要給輔助指針，幫助完成小孩出圈
    Boy helper=first;
    //需要?jiǎng)?chuàng)建一個(gè)輔助指針（變量）helper，事先應(yīng)該指向環(huán)形鏈表的最后這個(gè)節(jié)點(diǎn)
    while(true){
        if(helper.getNext()==first){//說明helper指向最后小孩節(jié)點(diǎn)
            break;
        }
        helper=helper.getNext();
    }
    //小孩報(bào)數(shù)前，先讓first和helper移動(dòng)k-1次
    for(int j=0;j<startNo-1;j++){
        first=first.getNext();
        helper=helper.getNext();
    }
    //當(dāng)小孩報(bào)數(shù)時(shí)，讓first和helper這個(gè)指針同時(shí)的移動(dòng)m-1次,然后出圈
    //這里是一個(gè)循環(huán)操作，直到圈中只有一個(gè)節(jié)點(diǎn)
    while(true){
        if(helper==first){  //說明圈中只有一個(gè)節(jié)點(diǎn)
            break;
        }
        //讓first和helper指針同時(shí)移動(dòng)countnum-1次
        for(int j=0;j<countNum-1;j++){
            first=first.getNext();
        helper=helper.getNext();
        }
        //這時(shí)first指向的節(jié)點(diǎn)，就是要出圈的小孩節(jié)點(diǎn)
        first=first.getNext();
        helper.setNext(first);
        
    }
    System.out.printf("最后留在圈中的小孩編號為%d\n",first.getNo());
}

下期預(yù)告：力扣每日一練之?dāng)?shù)組中篇Day2

覺得文章寫的不錯(cuò)的親親們，點(diǎn)贊評論走一波，愛你們哦！??

結(jié)束語??????
??推薦一款模擬面試、刷題神器網(wǎng)站
點(diǎn)擊跳轉(zhuǎn)進(jìn)入網(wǎng)站點(diǎn)擊進(jìn)入
1、算法篇（398題）：面試必刷100題、算法入門、面試高頻榜單
2、SQL篇（82題）：快速入門、SQL必知必會(huì)、SQL進(jìn)階挑戰(zhàn)、面試真題
3、大廠筆試真題：字節(jié)跳動(dòng)、美團(tuán)、百度、騰訊…文章來源地址http://www.zghlxwxcb.cn/news/detail-401958.html

到了這里，關(guān)于新星計(jì)劃Day6【數(shù)據(jù)結(jié)構(gòu)與算法】 鏈表Part2的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！