• 鏈表(Linked List) 介紹
• 單鏈表的思路分析
• 單鏈表的代碼實(shí)現(xiàn)
• 單鏈表的面試題
• 雙向鏈表的思路分析
• 雙向鏈表的代碼實(shí)現(xiàn)
• 單向環(huán)形鏈表和Josephu(約瑟夫)問(wèn)題

1. 鏈表(Linked List)的介紹

• 鏈表是有序的列表疹尾，但在內(nèi)存中存儲(chǔ)不一定連續(xù)

1. 鏈表是以節(jié)點(diǎn)的方式來(lái)存儲(chǔ)的，是 鏈?zhǔn)酱鎯?chǔ)
2. 每個(gè)節(jié)點(diǎn)包含 data 域， next 域：指向下一個(gè)節(jié)點(diǎn)
3. 鏈表的各個(gè)節(jié)點(diǎn)不一定連續(xù)存儲(chǔ)
4. 鏈表分 帶頭節(jié)點(diǎn)的鏈表 和 不帶頭節(jié)點(diǎn)的鏈表，根據(jù)實(shí)際需求來(lái)確定

• 帶頭節(jié)點(diǎn)的單鏈表的邏輯結(jié)構(gòu)圖如下

2. 單鏈表的思路分析

• 使用帶 head 頭結(jié)點(diǎn)的單鏈表實(shí)現(xiàn) - 水滸英雄排行榜管理完成對(duì)英雄任務(wù)的增刪改查操作。

2.1 添加，方式一

• 添加英雄時(shí)，直接添加到鏈表尾部

• 思路示意圖

• 思路分析：

  添加（創(chuàng)建）

  ① 先創(chuàng)建一個(gè) head 頭節(jié)點(diǎn)谴垫，作用是表示單鏈表的頭

  ② 后面添加節(jié)點(diǎn)時(shí)，直接加到鏈表的最后

  遍歷：

  通過(guò)定義一個(gè)輔助變量母蛛，來(lái)幫助遍歷整個(gè)鏈表翩剪。

2.2 添加，方式二

• 添加英雄時(shí)彩郊，根據(jù)排名 將英雄插入到指定位置（如果有這個(gè)排名前弯，添加失敗蚪缀，并給出提示）

• 思路分析：

  ① 首先找到新添加節(jié)點(diǎn)的位置，通過(guò)輔助變量（指針）遍歷

  ② 新的節(jié)點(diǎn).next = temp.next;

  ③ temp = 新的節(jié)點(diǎn)

2.3 修改節(jié)點(diǎn)

• 思路分析

  ① 先找到該節(jié)點(diǎn)恕出，通過(guò)輔助變量（指針）询枚，遍歷

  ② temp.name = newHeroNode.name

  ③ temp.nickname = newHeroNode.nickname

2.4 刪除節(jié)點(diǎn)

• 示意圖

• 思路分析

  ① 先找到該節(jié)點(diǎn)，通過(guò)輔助變量（指針）浙巫，遍歷

  ② temp.next = temp.next.next

  ③ 被刪除的節(jié)點(diǎn)金蜀，將不會(huì)有其它引用指向，將會(huì)被垃圾回收機(jī)制回收

3. 單鏈表代碼實(shí)現(xiàn)

• 定義節(jié)點(diǎn)

//定義 HeroNode的畴， 每個(gè)HeroNode 對(duì)象就是一個(gè)節(jié)點(diǎn)
class HeroNode{
    public int no;
    public String name;
    public String nickname;
    public HeroNode next; //指向下一個(gè)節(jié)點(diǎn)
    //構(gòu)造器
    public HeroNode(int no,String name,String nickname){
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }
    //為了顯示方便渊抄，我們重寫(xiě)toString

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}

• 定義單鏈表

//定義 SingleLinkedList 管理我們的英雄
class SingleLinkedList{
    //先初始化一個(gè)頭節(jié)點(diǎn)，頭節(jié)點(diǎn)不要?jiǎng)?    private HeroNode head = new HeroNode(0,"","");

    public HeroNode getHead() {
        return head;
    }

    //添加節(jié)點(diǎn)到單向鏈表
    //思路：當(dāng)不考慮編號(hào)順序時(shí)
    //1. 找到當(dāng)前鏈表的最后節(jié)點(diǎn)
    //2. 將最后這個(gè)節(jié)點(diǎn)的next 指向 新的節(jié)點(diǎn)
    public void add(HeroNode heroNode){
        //因?yàn)閔ead 節(jié)點(diǎn)不能動(dòng)苗傅，因此我們需要一個(gè)輔助遍歷 temp
        HeroNode temp = head;
        //遍歷鏈表，找到最后
        while(true){
             //找到鏈表的最后
            if(temp.next == null){
                break;
            }
            //如果沒(méi)有找到最后班巩，將 temp 后移
            temp = temp.next;
        }
        //當(dāng)退出 while 循環(huán)時(shí)渣慕，temp就指向了鏈表的最后
        //將最后這個(gè)節(jié)點(diǎn)的next 指向新的節(jié)點(diǎn)
        temp.next = heroNode;
    }

    //第二種方式在添加英雄時(shí)，根據(jù)排名將英雄插入到指定位置
    //（如果有這個(gè)排名抱慌，則添加失敗逊桦，并給出提示）
    public void addByOrder(HeroNode heroNode){
        //因?yàn)轭^節(jié)點(diǎn)不能動(dòng)，因此我們?nèi)匀煌ㄟ^(guò)一個(gè)輔助指針（變量）來(lái)幫助找到添加的位置
        //因?yàn)閱捂湵硪纸驗(yàn)槲覀冋业膖emp 是位于添加位置的前一個(gè)節(jié)點(diǎn)强经，否則插入不了
        HeroNode temp = head;
        boolean flag = false; //flag標(biāo)志添加的編號(hào)是否存在，默認(rèn)為false
        while(true){
            if(temp.next == null) { //說(shuō)明temp已經(jīng)在鏈表的最后
                break; //
            }
            if(temp.next.no > heroNode.no){ //位置找到了寺渗，就在temp之后插入
                break;

            }else if(temp.next.no == heroNode.no){ //說(shuō)明希望添加的 heroNode 的編號(hào)已然存在
                flag = true; //說(shuō)明編號(hào)存在
                break;
            }
            temp = temp.next; //后移匿情，遍歷當(dāng)前鏈表
        }
        //判斷 flag 的值
        if(flag){ //不能添加，說(shuō)明編號(hào)存在
            System.out.printf("準(zhǔn)備插入的英雄編號(hào) %d 已經(jīng)存在了信殊，不能加入\n",heroNode.no);
        }else{
            //插入到鏈表中炬称，temp的后面
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    //修改節(jié)點(diǎn)的信息，根據(jù)no編號(hào)來(lái)修改涡拘，即no編號(hào)不能改
    //說(shuō)明
    //1.根據(jù)newHeroNode 的 no 來(lái)修改即可
    public void update(HeroNode newHeroNode){
        //判斷是否空
        if(head.next == null){
            System.out.println("鏈表為空~");
            return;
        }
        //找到需要修改的節(jié)點(diǎn)玲躯，根據(jù)no編號(hào)
        //定義一個(gè)輔助變量
        HeroNode temp = head.next;
        boolean flag = false; //表示是否找到該節(jié)點(diǎn)
        while(true){
            if(temp == null){
                break; //已經(jīng)遍歷完鏈表
            }
            if(temp.no == newHeroNode.no){
                //找到了
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //根據(jù)flag 判斷是否找到要修改的節(jié)點(diǎn)
        if (flag) {
            temp.name = newHeroNode.name;
            temp.nickname = newHeroNode.nickname;
        }else{ //沒(méi)有找到
            System.out.printf("沒(méi)有找到 編號(hào) %d 的節(jié)點(diǎn)，不能修改\n",newHeroNode.no);
        }
    }

    //刪除節(jié)點(diǎn)
    //思路
    //1. head 不能動(dòng)鳄乏，因此我們需要一個(gè) temp 輔助節(jié)點(diǎn)找到待刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
    //2. 說(shuō)明我們?cè)诒容^時(shí)跷车，是temp.next.no 和 需要?jiǎng)h除的節(jié)點(diǎn)的 no 比較
    public void del(int no){
        HeroNode temp = head;
        boolean flag = false; // 標(biāo)志是否找到待刪除節(jié)點(diǎn)的
        while(true){
            if(temp.next == null){ //已經(jīng)到鏈表的最后
                break;
            }
            if(temp.next.no == no){
                //找到了待刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的temp
                flag = true;
                break;
            }
            temp = temp.next; //temp后移，遍歷
        }
        //判斷 flag
        if(flag){ //刪除
            //可以刪除
            temp.next = temp.next.next;
        }else{
            System.out.printf("要?jiǎng)h除的 %d 節(jié)點(diǎn)不存在\n",no);
        }
    }

    //顯示鏈表【遍歷】
    public void list(){
        //判斷鏈表是否為空
        if(head.next == null){
            System.out.println("鏈表為空");
            return;
        }
        //因?yàn)轭^節(jié)點(diǎn)橱野，不能動(dòng)，因此我們需要一個(gè)輔助變量來(lái)遍歷
        HeroNode temp = head.next;
        while(true){
            //判斷是否到鏈表最后
            if(temp == null){
                break;
            }
            //輸出節(jié)點(diǎn)的信息
            System.out.println(temp); //已經(jīng)重寫(xiě)toString
            //將temp 后移不铆，一定要小心
            temp = temp.next;
        }
    }
}

• 測(cè)試類

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //進(jìn)行測(cè)試
        //先創(chuàng)建節(jié)點(diǎn)
        HeroNode hero1 = new HeroNode(2, "宋江", "及時(shí)雨");
        HeroNode hero2 = new HeroNode(4, "盧俊義", "玉麒麟");
        HeroNode hero3 = new HeroNode(6, "吳用", "智多星");
        HeroNode hero4 = new HeroNode(8, "林沖", "豹子頭");

        //創(chuàng)建一個(gè)鏈表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        //加入
//        singleLinkedList.add(hero1);
//        singleLinkedList.add(hero4);
//        singleLinkedList.add(hero2);
//        singleLinkedList.add(hero3);
        //加入按照編號(hào)的順序
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);
        singleLinkedList.addByOrder(hero4);
//        singleLinkedList.addByOrder(hero3);

        
        /*//顯示一把
        singleLinkedList.list();


        //測(cè)試修改節(jié)點(diǎn)的代碼
        HeroNode newHeroNode = new HeroNode(2,"小盧","玉麒麟~~");
        singleLinkedList.update(newHeroNode);

        System.out.println("修改之后的鏈表情況~~");
        singleLinkedList.list();

        //刪除一個(gè)節(jié)點(diǎn)
        singleLinkedList.del(1);
        singleLinkedList.del(4);
//        singleLinkedList.del(2);
//        singleLinkedList.del(3);
//        singleLinkedList.del(5);
        System.out.println("刪除后鏈表情況~~");
        singleLinkedList.list();

    }
    
}

4. 單鏈表有關(guān)的面試題

4.1 求單鏈表中有效節(jié)點(diǎn)的個(gè)數(shù)

//方法：獲取到單鏈表的節(jié)點(diǎn)的個(gè)數(shù)（如果是帶頭節(jié)點(diǎn)的鏈表，需求不統(tǒng)計(jì)頭節(jié)點(diǎn)）
    /**
     *
     * @param head 鏈表的頭節(jié)點(diǎn)
     * @return 返回的就是有效節(jié)點(diǎn)的個(gè)數(shù)
     */
    public static int getLength(HeroNode head){
        if(head.next == null){ //空鏈表
            return 0;
        }
        int length = 0;
        //定義一個(gè)輔助變量,這里沒(méi)有統(tǒng)計(jì)頭節(jié)點(diǎn)的個(gè)數(shù)
        HeroNode cur = head.next;
        while(cur != null){
            length++;
            cur = cur.next;
        }
        return length;
    }

4.2 查找單鏈表中的倒數(shù)第k個(gè)節(jié)點(diǎn)

• 思路分析

  ① 編寫(xiě)一個(gè)方法只洒，接收 head 節(jié)點(diǎn)劳坑，同時(shí)接收一個(gè) index

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

  ③ 先把鏈表從頭到尾遍歷毕谴，得到鏈表的總長(zhǎng)度 size = getLength(head);

  ④ 得到總長(zhǎng)度 size 后养葵，就從鏈表的第一個(gè)開(kāi)始遍歷 （size - index）個(gè)护赊，就可得到

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

//查找單鏈表中倒數(shù)第K個(gè)結(jié)點(diǎn)
    //思路
    //1. 編寫(xiě)一個(gè)方法寻馏，接收head節(jié)點(diǎn)诚欠，同時(shí)接收一個(gè)index
    //2. index 表示是倒數(shù)第 index 個(gè)節(jié)點(diǎn)
    //3. 先把鏈表從頭到尾遍歷轰绵，得到鏈表的總長(zhǎng)度getLength
    //4. 得到size 后藏澳，我們從鏈表的第一個(gè)開(kāi)始遍歷（size-index）個(gè)翔悠，就可以得到
    //5. 如果找到了蓄愁，則返回該節(jié)點(diǎn)撮抓，否則返回null
    public static HeroNode findLastIndexNode(HeroNode head, int index){
        //判斷如果鏈表為空丹拯，返回null
        if(head.next == null){
            return  null; //沒(méi)有找到
        }
        //第一個(gè)遍歷得到鏈表的長(zhǎng)度（節(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;
    }

4.3 單鏈表的反轉(zhuǎn)

• 示意圖

  
  

• 思路分析：

  ① 先定義一個(gè)節(jié)點(diǎn) reverseHead = new HeroNode()

  ② 從頭到尾遍歷原來(lái)的鏈表咬像，每遍歷一個(gè)節(jié)點(diǎn)县昂，就將其取出审洞，并放到新的reverseHead的 最前端

  ③ 原來(lái)的鏈表的 head.next = reverseHead.next

• 代碼實(shí)現(xiàn)

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

    }

4.4 從尾到頭打印單鏈表

• 方式一：先將單鏈表反轉(zhuǎn)抛人，再遍歷，但這樣會(huì)破壞單鏈表原有的結(jié)構(gòu)

• 方式二：利用 棧的特性，將各個(gè)節(jié)點(diǎn)壓入棧中，利用棧 先進(jìn)后出的特性，實(shí)現(xiàn)逆序打印臼隔，

• 方式二的代碼實(shí)現(xiàn)：

//可以利用棧這個(gè)數(shù)據(jù)結(jié)構(gòu)氨淌，將各個(gè)節(jié)點(diǎn)壓入到棧中奢浑，然后利用棧的先進(jìn)后出的特點(diǎn)即寡，就實(shí)現(xiàn)了逆序打印的效果
    public static void reversePrint(HeroNode head){
        if(head.next == null){
            return; // 空鏈表著蟹，不能打印
        }
        //創(chuàng)建一個(gè)棧奸披，將各個(gè)節(jié)點(diǎn)壓入棧
        Stack<HeroNode> stack = new Stack<>();
        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)后出
        }

    }

4.5 合并兩個(gè)有序單鏈表蜓竹，合并之后的鏈表依然有序

• 思路分析：

  ① 當(dāng)兩個(gè)鏈表都為空時(shí)邑茄，直接返回 null

  ② 當(dāng)一個(gè)鏈表為空，另一個(gè)不為空時(shí)，直接加到新鏈表上 head3 = head2.next;

  ③ 兩個(gè)都不為空時(shí)，先將鏈表1加載到新鏈表上head3.next = head1.next奈偏，然后遍歷新的鏈表（head3）裁蚁，找到第一個(gè)大于l鏈表2的節(jié)點(diǎn)移必，然后將鏈表2的一個(gè)節(jié)點(diǎn)插入到新鏈表的位置

  如果鏈表3遍歷完了舞萄，但鏈表2還未插入完含思，直接將剩余的插到新鏈表的末尾
  

//合并兩個(gè)有序單鏈表，合并之后的鏈表依然有序
    //思路：當(dāng)兩個(gè)鏈表為空時(shí)，直接返回饰抒，當(dāng)一個(gè)為空仗处，另不為空時(shí)咒精，直接加在新鏈表上鞋屈，當(dāng)兩個(gè)都不為空時(shí)，將
    //先將小的鏈表加載新鏈表上拄氯，
    public static void combineTwoLinkedList(HeroNode head1,HeroNode head2,HeroNode head3){
        //如果兩個(gè)鏈表均為空，則無(wú)需合并，直接返回
        if(head1.next == null && head2.next == null){
            return;
        }
        //如果鏈表1為空，則將head3.next指向head2.next,實(shí)現(xiàn)鏈表2中節(jié)點(diǎn)連接到鏈表3
        if(head1.next == null || head2.next == null){
            if(head1.next == null){
                head3.next = head2.next;
            }else{
                head3.next = head1.next;
            }
            
        }else{
            //將head3.next指向 head1.next,實(shí)現(xiàn)鏈表1的節(jié)點(diǎn)連接到鏈表3上
            head3.next = head1.next;
            //定義一個(gè)輔助的指針（變量）侣签，幫助我們遍歷鏈表2
            HeroNode cur2 = head2.next;
            //定義一個(gè)輔助的指針（變量）僚碎，幫助遍歷鏈表3
            HeroNode cur3 = head3;
            HeroNode next = null;
            //遍歷鏈表2矛双，將其節(jié)點(diǎn)按順序連接至鏈表3
            while(cur2 != null){
                //鏈表3遍歷完畢后十减，可以直接將鏈表2剩下的節(jié)點(diǎn)連接至鏈表3的末尾
                if(cur3.next == null){
                    cur3.next = cur2;
                    break;
                }
                //在鏈表3中，找到第一個(gè)大于鏈表2中的節(jié)點(diǎn)編號(hào)的節(jié)點(diǎn)
                //因?yàn)槭菃捂湵砩置业降墓?jié)點(diǎn)cur3.next是位于添加位置的前一個(gè)節(jié)點(diǎn)甥郑，否則無(wú)法插入
                if(cur2.no <= cur3.next.no){
                    next = cur2.next; //先暫時(shí)保存鏈表2中當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)店展，方便后續(xù)使用
                    cur2.next = cur3.next; //將cur2 的下一個(gè)節(jié)點(diǎn)指向 cur3的下一個(gè)節(jié)點(diǎn)
                    cur3.next = cur2; //將cur2 連接到 鏈表3上
                    cur2 = next; //將cur2 后移
                }
                //遍歷鏈表3
                cur3 = cur3.next;
            }
        }

    }

5. 雙向鏈表的思路分析

5.1 單向鏈表缺點(diǎn)分析

• 查找方向只能是一個(gè)方向，而雙向鏈表可以向前或者向后查找
• 不能自我刪除糖赔，需要依靠輔助節(jié)點(diǎn)基茵。而雙向鏈表宴咧，可以自我刪除。
  • 單鏈表刪除節(jié)點(diǎn)時(shí)假抄，總是要找到temp（待刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)）

5.2 雙向鏈表的思路分析

• 遍歷

  和單鏈表相同，只是可以向前，也可以向后查找

• 添加（方式一：添加到雙向鏈表的最后）

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

  ② temp.next = newHeroNode;

  ③ newHeroNode.pre = temp;

• 添加（方式二：按順序添加指定位置）

  ① 通過(guò)一個(gè)輔助指針遍歷尋找添加的位置

  ② 如果遍歷到最后了铭乾，直接添加到最后

  ③ 如果找到 temp.next.no > heroNode.no ,就在 temp 后面插入，

  `temp.next == null`時(shí) `temp.next = heroNode;heroNode.pre = temp;`
  
  `temp.next != null`時(shí) `temp.next = heroNode.next; temp.next.pre = heroNode;`
  

  ④ 如果已經(jīng)存在就返回說(shuō)明已經(jīng)存在

• 修改

  ① 先找到要修改的節(jié)點(diǎn)的位置

  ② temp.name = newHeroNode.name

  ③ temp.nickname = newHerNode.nickname

• 刪除

  ① 直接找到要?jiǎng)h除的節(jié)點(diǎn)妇押，如temp

  ② temp.pre.next = temp.next

  ③ temp.next.pre = temp.pre

6. 雙向鏈表的代碼實(shí)現(xiàn)

• 節(jié)點(diǎn)類

//定義 HeroNode2 队贱，每個(gè)HeroNode 對(duì)象就是一個(gè)節(jié)點(diǎn)
class HeroNode2{
    public int no;
    public String name;
    public String nickname;
    public HeroNode2 next; //指向下一個(gè)節(jié)點(diǎn) 默認(rèn)為null
    public HeroNode2 pre; //指向前一個(gè)節(jié)點(diǎn) 默認(rèn)為null

    //構(gòu)造器
    public HeroNode2(int no,String name,String nickname){
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    //為了顯示方法与学，我們重新toString

    @Override
    public String toString() {
        return "HeroNode2{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}

• 雙向鏈表類

//創(chuàng)建一個(gè)雙向鏈表類
class DoubleLinkedList{

    //先初始化一個(gè)頭節(jié)點(diǎn)，頭節(jié)點(diǎn)不要?jiǎng)樱淮娣啪唧w的數(shù)據(jù)
    private HeroNode2 head = new HeroNode2(0,"","");

    //返回頭節(jié)點(diǎn)
    public HeroNode2 getHead(){
        return head;
    }

    //順序添加
    public void addByOrder(HeroNode2 heroNode){
        //因?yàn)轭^節(jié)點(diǎn)不能動(dòng)衙解，因此我們?nèi)匀煌ㄟ^(guò)一個(gè)輔助指針來(lái)幫助找到添加的位置
        HeroNode2 temp = head;
        boolean flag = false; //flag 標(biāo)志添加編號(hào)是否存在暑椰，默認(rèn)為 false
        while(true){
            if(temp.next == null){ //說(shuō)明 temp 已經(jīng)到鏈表的最后了
                break;
            }
            if(temp.next.no > heroNode.no){ //位置找到，就在temp的后面插入
                break;
            }else if(temp.next.no == heroNode.no){ //說(shuō)明希望添加的 heroNode 的編號(hào)已經(jīng)存在
                flag = true; //說(shuō)明編號(hào)存在
                break;
            }
            temp = temp.next;
        }
        //判斷 flag 的值
        if(flag){ //不能添加戳鹅，說(shuō)明編號(hào)存在
            System.out.printf("準(zhǔn)備插入的英雄的編號(hào) %d 已經(jīng)存在了爬虱，不能加入了 \n",heroNode.no);
        }else{
            //插入到鏈表中 temp 的后面
            if(temp.next != null){
                heroNode.next = temp.next;
                temp.next.pre = heroNode;
            }
            temp.next = heroNode;
            heroNode.pre = temp;

        }
    }

    //修改一個(gè)節(jié)點(diǎn)的內(nèi)容,可以看到雙向鏈表的節(jié)點(diǎn)內(nèi)容修改和單向鏈表一樣
    public void update(HeroNode2 newHeroNode){
        //判斷是否空
        if(head.next == null){
            System.out.println("鏈表為空~");
            return;
        }
        //找到需要修改的節(jié)點(diǎn)曲梗，根據(jù)no編號(hào)
        //定義一個(gè)輔助變量
        HeroNode2 temp = head.next;
        boolean flag = false; //表示是否找到該節(jié)點(diǎn)
        while(true){
            if(temp == null){
                break; //已經(jīng)遍歷完畢
            }
            if(temp.no == newHeroNode.no){
                //找到
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //根據(jù) flag 判斷是否找到要修改的節(jié)點(diǎn)
        if(flag) {
            temp.name = newHeroNode.name;
            temp.nickname = newHeroNode.nickname;
        }else{ //沒(méi)有找到
            System.out.printf("沒(méi)有找到編號(hào) %d 的節(jié)點(diǎn),不能修改\n",newHeroNode.no);

        }
    }

    //添加一個(gè)節(jié)點(diǎn)到雙向鏈表的最后
    public void add(HeroNode2 heroNode){
        //因?yàn)?head 節(jié)點(diǎn)不能動(dòng)定罢，因此我們需要一個(gè)輔助遍歷 temp
        HeroNode2 temp = head;
        //遍歷鏈表蝙场，找到最后
        while(true){
            //找到鏈表的最后
            if(temp.next == null){
                break;
            }
            //如果沒(méi)有找到最后台诗，將temp后移
            temp = temp.next;
        }
        //當(dāng)退出 while 循環(huán)時(shí)粱快， temp就指向了鏈表的最后
        //形成雙向鏈表
        temp.next = heroNode;
        heroNode.pre = temp;
    }

    //遍歷雙向鏈表
    public void list(){
        //判斷鏈表是否為空
        if(head.next == null){
            System.out.println("鏈表為空");
            return;
        }
        //因?yàn)轭^節(jié)點(diǎn)，不能動(dòng)谤辜，因此我們需要一個(gè)輔助變量來(lái)遍歷
        HeroNode2 temp = head.next;
        while(true){
            //判斷是否到鏈表最后
            if(temp == null){
                break;
            }
            //輸出節(jié)點(diǎn)的信息
            System.out.println(temp);
            //將 temp 后移结蟋，一定小心
            temp = temp.next;
        }
    }

    //從雙向鏈表中刪除一個(gè)節(jié)點(diǎn)
    //說(shuō)明
    //1 對(duì)于雙向鏈表胳岂，我們可以直接找到要?jiǎng)h除節(jié)點(diǎn)
    //2 找到后产园，自我刪除即可
    public void del(int no){
        //判斷當(dāng)前鏈表是否為空
        if(head.next == null){ //空鏈表
            System.out.println("鏈表為空竞端，無(wú)法刪除");
            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;
            //這里我們的代碼由問(wèn)題，當(dāng)刪除最后那個(gè)節(jié)點(diǎn)
            //如果是最后一個(gè)節(jié)點(diǎn)仇穗，就不需要執(zhí)行下面這句話仪缸，否則出現(xiàn)空指針
            //temp.next = null.pre 空指針異常
            if(temp.next != null){
                temp.next.pre = temp.pre;
            }
        }else{
            System.out.printf("要?jiǎng)h除的 %d 節(jié)點(diǎn)不存在\n",no);
        }
    }
}

• 測(cè)試類

public class DoubleLinkedListDemo {
    public static void main(String[] args) {
        //測(cè)試
        System.out.println("雙向鏈表的測(cè)試");
        //先創(chuàng)建節(jié)點(diǎn)
        HeroNode2 hero1 = new HeroNode2(2, "宋江", "及時(shí)雨");
        HeroNode2 hero2 = new HeroNode2(4, "盧俊義", "玉麒麟");
        HeroNode2 hero3 = new HeroNode2(6, "吳用", "智多星");
        HeroNode2 hero4 = new HeroNode2(8, "林沖", "豹子頭");

        //創(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(4);
//        System.out.println("刪除后的鏈表");
//        doubleLinkedList.list();


        //順序添加
        doubleLinkedList.addByOrder(hero3);
        doubleLinkedList.addByOrder(hero2);
        doubleLinkedList.addByOrder(hero4);
        doubleLinkedList.addByOrder(hero1);
        System.out.println("順序添加結(jié)果");
        doubleLinkedList.list();
    }

}

7. 單向環(huán)形鏈表和Josephu(約瑟夫)問(wèn)題

7.1 Josephu 問(wèn)題

• 設(shè)編號(hào)為 1宾茂，2跨晴，... n 的 n 個(gè)人圍坐在一圈端盆，約定編號(hào)為k（1<=k<=n）的人從1 開(kāi)始報(bào)數(shù)焕妙，數(shù)到 m 的人出列，它的下一位又從 1 開(kāi)始報(bào)數(shù)末患，數(shù)到 m 的那個(gè)人又出列璧针，依次類推探橱，直到所有人出列位置虽抄，由此產(chǎn)生了一個(gè)出隊(duì)編號(hào)序列迈窟。

• 提示：用一個(gè)不帶頭節(jié)點(diǎn)的循環(huán)鏈表來(lái)處理 Josephu 問(wèn)題

  先構(gòu)成一個(gè) 有 n 個(gè)節(jié)點(diǎn)的單循環(huán)鏈表

  然后從k 節(jié)點(diǎn)起從 1 開(kāi)始計(jì)數(shù)曲稼，計(jì)到 m 時(shí)贫悄，對(duì)應(yīng)節(jié)點(diǎn)從鏈表中刪除

  然后再?gòu)谋粍h除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)再?gòu)?1 開(kāi)始計(jì)數(shù)娘摔，直到最后一個(gè)被刪除為止

7.2 創(chuàng)建環(huán)形鏈表思路分析

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

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

  ② 后面每創(chuàng)建一個(gè)新節(jié)點(diǎn)逆趋，就把該節(jié)點(diǎn)闻书，加入到已有環(huán)形鏈表中

• 遍歷環(huán)形鏈表

  ① 先讓輔助指針 curBoy ,指向 first 節(jié)點(diǎn)

  ② 然后通過(guò)一個(gè) while 循環(huán)遍歷該環(huán)形鏈表 curBoy.next == first 結(jié)束

7.3 小孩出圈的思路分析

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

  n = 5,即有5人
  k = 1,從第一個(gè)人開(kāi)始報(bào)數(shù)
  m = 2,數(shù)2下
  

① 創(chuàng)建一個(gè)輔助指針 helper 杆融，事先應(yīng)該指向環(huán)形鏈表的最后一個(gè)節(jié)點(diǎn)脾歇。

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

② 當(dāng)小孩報(bào)數(shù)時(shí)激况，讓 first 和 helper 同時(shí)移動(dòng) m - 1次

③ 將 first 指向的小孩節(jié)點(diǎn)出圈乌逐，

first=first.next helper.next=first

原來(lái)first 指向的節(jié)點(diǎn)浙踢，沒(méi)有任何引用指向洛波，就會(huì)被回收

• 出圈的順序?yàn)椋?->4->1->5->3

7.4 代碼實(shí)現(xiàn)

• 創(chuàng)建一個(gè)小孩節(jié)點(diǎn)類

//創(chuàng)建一個(gè) Boy 類蹬挤，表示一個(gè)節(jié)點(diǎn)
class Boy{
    private int no; //編號(hào)
    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;
    }
}

• 創(chuàng)建單向環(huán)形鏈表

//創(chuàng)建一個(gè)環(huán)形的單向鏈表
class CircleSingleLinkedList{
    //創(chuàng)建一個(gè) first 節(jié)點(diǎn)吨悍，當(dāng)前沒(méi)有編號(hào)
    private Boy first = new Boy(-1);
    //添加小孩的節(jié)點(diǎn)畜份，構(gòu)建成一個(gè)環(huán)形鏈表
    public void addBoy(int nums){ //nums 節(jié)點(diǎn)的數(shù)量
        // nums 做一個(gè)數(shù)據(jù)校驗(yàn)
        if(nums < 1){
            System.out.println("nums 的值不正確");
            return;
        }
        Boy curBoy  = null; //輔助指針爆雹，幫助我們構(gòu)建環(huán)形鏈表
        //使用 for 來(lái)創(chuàng)建我們的環(huán)形鏈表
        for(int i = 1; i <= nums; i++){
            //根據(jù)編號(hào)钙态，創(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è)小孩 蚓挤，因?yàn)閒irst 不能動(dòng)
            }else{
                curBoy.setNext(boy); //先將curBoy 從指向first 改變指向 新節(jié)點(diǎn)boy
                boy.setNext(first); //讓新節(jié)點(diǎn) boy 指向 first
                curBoy = boy;  //然后后移curBoy, 為下一次添加做準(zhǔn)備
            }
        }

    }
    //遍歷當(dāng)前環(huán)形鏈表
    public void showBoy(){
        //判斷鏈表是否為空
        if(first == null){
            System.out.println("沒(méi)有任何小孩");
            return;
        }
        //因?yàn)?first 不能動(dòng)灿意，因此我們?nèi)匀皇褂靡粋€(gè)輔助指針
        Boy curBoy = first;
        while (true){
            System.out.printf("小孩的編號(hào) %d \n",curBoy.getNo());
            if(curBoy.getNext() == first){ //說(shuō)明已經(jīng)遍歷完畢
                break;
            }
            curBoy = curBoy.getNext(); //curBoy 后移
        }
    }

    //根據(jù)用戶的輸入缤剧，計(jì)算小孩出圈的順序

    /**
     *
     * @param startNo 表示從第幾個(gè)小孩開(kāi)始數(shù)數(shù)
     * @param countNum 表示數(shù)幾下
     * @param nums 表示最初有多少小孩在圈中
     */
    public void countBoy(int startNo,int countNum,int nums){
       //先對(duì)數(shù)據(jù)進(jìn)行校驗(yàn)
       if(first == null || startNo < 1 || startNo > nums){
           System.out.println("參數(shù)輸入有誤，請(qǐng)重新輸入");
           return;
       }
       //創(chuàng)建一個(gè)輔助指針抵窒，幫助完成小孩出圈
        Boy helper = first;
       //需求創(chuàng)建一個(gè)輔助指針（變量）helper 李皇，事先應(yīng)該指向環(huán)形鏈表的最后這個(gè)節(jié)點(diǎn)
        while(true){
            if(helper.getNext() == first){ //說(shuō)明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ù)前圃阳，先讓first 和 helper 指針同時(shí)移動(dòng) m -1 次捍岳，然后出圈
        //這里是一個(gè)循環(huán)操作锣夹，知道圈中只有一個(gè)節(jié)點(diǎn)
        while(true){
            if(helper == first){ //說(shuō)明圈中只有一個(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)
            System.out.printf("小孩 %d 出圈\n",first.getNo());
            //這時(shí)將 first 指向的小孩節(jié)點(diǎn)出圈
            first = first.getNext();
            helper.setNext(first);
        }
        System.out.printf("最后留在圈中的小孩編號(hào) %d \n",helper.getNo());
    }
}

• 測(cè)試出圈順序

public class Josepfu {
    public static void main(String[] args) {
        //測(cè)試構(gòu)建環(huán)形鏈表搀绣，和遍歷是否正確
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.addBoy(5); //加入5個(gè)小孩節(jié)點(diǎn)
        circleSingleLinkedList.showBoy();

        //測(cè)試一把小孩出圈是否正確
        circleSingleLinkedList.countBoy(1,2,5); //2-4-1-5-3
    }
}