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

一、双向链表

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 节点不能动，因此我们需要一个辅助变量 tempHeroNode2 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){//找到待删除节点的前一个节点 tempflag = true;break;}temp = temp.next;   //后移继续遍历}//判断flagif (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;       //指向下一个节点，默认为 nullpublic HeroNode2 pre;        //指向前一个节点，默认为 null//构造器public HeroNode2(int no, String name, String nickname){this.no = no;this.name = name;this.nickname = nickname;}//为了显示方法，我们重新 toString@Overridepublic String toString() {return "HeroNode{" +"no=" + no +", name='" + name + '\'' +", nickname='" + nickname + '\'' +'}';}
}

java怎么实现链表？

二、约瑟夫问题

1.环形列表介绍

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

2.问题来历

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

一般形式

java链表数据结构，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;    //指向下一个节点，默认为 nullpublic 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;}
}

链表的顺序查找算法？