本文共 9480 字，大约阅读时间需要 31 分钟。

第三章 第三章 双向链表、环形链表以及约瑟夫问题

一、双向链表

1.双线链表对比单向链表的优点：

• 单向链表查找的方向只能是一个方向，而双向链表可以向前或者向后查找
• 单向链表不能自我删除，需要靠辅助节点，而双向链表可以自我删除。所以我们之前删除单链表是总是需要找到temp，temp是待删除节点的前一个节点

2.分析双向链表的遍历、添加、修改和删除的操作思路

• 遍历方式和单链表一样，只是可以向前，也可以向后查找
• 添加（默认添加到双向链表的最后）
  1.先找到双向链表的最后一个节点temp
  2.temp.next = new HeroNode;
  3.new HeroNode.pre = temp
• 修改的原理和单向链表一样
• 删除，因为双向链表的节点有前驱节点，所以可以实现某个节点的自我删除
  1.找到要删除的这个节点temp
  2.temp.pre.next = temp.next
  3.temp.next.pre = temp.pre

3.代码实现

package com.sisyphus.linkedlist;public class DoubleLinkedListDemo {
       public static void main(String[] args) {
           //测试        System.out.println("双向链表的测试");        //先创建节点        HeroNode2 hero1 = new HeroNode2(1,"宋江","及时雨");        HeroNode2 hero2 = new HeroNode2(2,"卢俊义","玉麒麟");        HeroNode2 hero3 = new HeroNode2(3,"吴用","智多星");        HeroNode2 hero4 = 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();    }}//创建一个双向链表的类class DoubleLinkedList{
       //先初始化一个头节点，头节点不能动，否则会找不到这个链表    private HeroNode2 head = new HeroNode2(0,"","");    //返回头节点    public HeroNode2 getHead() {
           return head;    }    //遍历双向链表的方法    //展示链表    //借助temp辅助变量，遍历整个链表    public void list(){
           //判断链表是否为空        if(head.next == null){
               System.out.println("链表为空");            return;        }        //因为头节点不能动，因此我们需要一个辅助变量来遍历        HeroNode2 temp = head.next;        while(true){
               //判断是否在链表的尾部            if (temp == null){
                   break;            }            //输出节点信息            System.out.println(temp);            //将 temp 后移            temp = temp.next;        }    }    //添加一个节点到双向链表的最后    public void add(HeroNode2 heroNode2){
           //因为 head 节点不能动，因此我们需要一个辅助变量 temp        HeroNode2 temp = head;        //遍历链表，找到最后        while(true){
               //找到链表的最后            if (temp.next == null){
                   break;            }            //如果没有找到最后，将 temp 后移            temp = temp.next;        }        //当退出 while 循环时，temp就指向了链表的最后        temp.next = heroNode2;        heroNode2.pre = temp;    }    //修改节点的信息，根据编号来修改，即编号不能修改    //说明    //1.根据 newHeroNode 的 no 来修改即可    //2.双向链表节点的修改和单链表几乎一样    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 = newHeroNode.name;            temp.nickname = newHeroNode.nickname;        }else{
                   //没有找到            System.out.printf("没有找到编号 %d 的节点",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;   //后移继续遍历        }        //判断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 HeroNode2 next;       //指向下一个节点，默认为 null    public HeroNode2 pre;        //指向前一个节点，默认为 null    //构造器    public HeroNode2(int no, 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 + '\'' +                '}';    }}

二、约瑟夫问题

1.环形列表介绍

• 没有头节点
• 节点有 next 域，指向下一个节点
• “最后一个节点”指向“第一个节点”

2.问题来历

据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决。Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏

一般形式

N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3。

3.思路

构建一个单向的环形链表

1. 先创建第一个节点，让 first 指向该节点，并让 next 指向自己形成环形
2. 后面我们每创建一个新的节点，就把该节点加入到已有的环形链表中即可

遍历环形链表

1. 先让一个辅助指针（变量）curBoy，指向 first 节点
2. 然后通过一个 while 循环遍历该环形链表即可，当 curPerson == first 时结束

根据用户的输入，生成出局顺序

1. 需要创建一个辅助变量 helper，事先应该指向环形链表的最后一个节点
2. 报数前先让 first 和 helper 移动 k - 1 次
3. 报数时，让 first 和 helper 同时移动 m - 1 次
4. 这时就可以将 first 指向的人出局 first = first.next ; helper.next = first 原来 first 指向的节点就没有任何引用，就会被回收

4.代码实现

package com.sisyphus.linkedlist;public class Josephu {
       public static void main(String[] args) {
           //测试，看看构建环形链表和遍历是否成功        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();        circleSingleLinkedList.addPerson(41);   //加入41个人        circleSingleLinkedList.showPerson();        //测试出局是否正确        circleSingleLinkedList.countPerson(1,3,41);    }}//创建一个环形的单向链表class CircleSingleLinkedList{
       //创建一个 first 节点，当前没有编号    private Person first = null;    //添加节点，构建成一个环形的链表    public void  addPerson(int nums){
           //对 nums 做一个数据校验        if (nums < 1){
               System.out.println("nums的值不正确");            return;        }        Person curPerson = null;    //辅助变量，帮助构建环形链表        //使用 for 来创建我们的环形链表        for (int i = 1; i <= nums; i++) {
               //根据编号创建节点            Person person = new Person(i);            //如果是第一个节点            if (i == 1){
                   first = person;                first.setNext(first);   //构成一个环                curPerson = first;         //让 curPerson 指向第一个节点            }else{
         //如果不是第一个节点                curPerson.setNext(person);                person.setNext(first);                curPerson = person;            }        }    }    //遍历当前环形链表    public void showPerson(){
           //判断链表是否为空        if (first == null){
               System.out.println("没有任何人");            return;        }        //因为 first 不能动，因此我们仍然使用一个辅助变量完成遍历        Person curPerson = first;        while(true){
               System.out.printf("编号%d \n",curPerson.getNo());            if (curPerson.getNext() == first){
     //说明已经遍历完毕                break;            }            curPerson = curPerson.getNext();    //curPerson 后移        }    }    //根据用户的输入，生成出局顺序    /**     *     * @param startNo   表示从第几个人开始报数     * @param countNum  表示数几下     * @param nums      表示最初有多少人在圈中     */    public void countPerson(int startNo,int countNum,int nums){
           //先对数据进行校验        if (first == null || startNo < 1 || startNo > nums){
               System.out.println("参数输入有误，请重新输入");            return;        }        //创建一个辅助指针，帮助完成出局        Person helper = first;        //让 helper 指向最后一个节点        while(true){
               if (helper.getNext() == first){
                   break;            }            helper = helper.getNext();        }        //报数前，让 first 和 helper 同时移动 startNo - 1 次        for (int i = 0; i < startNo - 1; i++) {
               first = first.getNext();            helper = helper.getNext();        }        //当报数时，让 first 和 helper 同时移动 countNum - 1 次，然后出局        //这里是一个循环操作，直到圈中只有一个节点        while(true){
               if (helper == first){
      //说明圈中只有一个节点                break;            }            //让 first 和 helper 同时移动 countNum - 1 次，然后出局            for (int i = 0; i < countNum - 1; i++) {
                   first = first.getNext();                helper = helper.getNext();            }            //这时 first 指向的节点，就是要出局的人            System.out.printf("编号%d出局\n",first.getNo());            //这时将 first 指向的人出局            first = first.getNext();            helper.setNext(first);        }        System.out.printf("最后活下来的人是编号%d",first.getNo());    }}//创建一个 Person 类，表示一个节点class Person{
       private int no; //编号    private Person next;    //指向下一个节点，默认为 null    public Person(int no){
           this.no = no;    }    public int getNo() {
           return no;    }    public void setNo(int no) {
           this.no = no;    }    public Person getNext() {
           return next;    }    public void setNext(Person next) {
           this.next = next;    }}

转载地址：http://rjyki.baihongyu.com/