双向链表的添加节点
双向链表删除节点
package com.caq.linkedlist;/** * 双向链表的增删改查 * * @Date 2021/12/10 12:24 * @Version 1.0 */public class DoubleLinkedDemo { public static void main(String[] args) { HeroNode2 head = new HeroNode2(2, "", ""); //双向链表的测试 HeroNode2 hero1 = new HeroNode2(1, "宋江", "及时雨"); HeroNode2 hero2 = new HeroNode2(2, "卢俊义", "玉麒麟"); HeroNode2 hero3 = new HeroNode2(3, "吴用", "智多星"); DoubleLinkedList doubleLinkedList = new DoubleLinkedList(); doubleLinkedList.add(hero1); doubleLinkedList.add(hero2); doubleLinkedList.add(hero3); doubleLinkedList.list(); //修改 HeroNode2 newHero = new HeroNode2(2, "BB", "CC"); doubleLinkedList.update(newHero); System.out.println("修改后的情况为"); doubleLinkedList.list(); }}class DoubleLinkedList { //生一个头结点 private HeroNode2 head = new HeroNode2(0, "", ""); //得到头结点 public HeroNode2 getHead() { return head; } //显示链表[遍历] 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.next; } } //添加节点到单向链表 public void add(HeroNode2 heroNode) { HeroNode2 temp = head; //遍历链表，找到最后 while (true) { //找到链表的最后 if (temp.next == null) { break; } //如果没有找到最后，就讲temp后移 temp = temp.next; } //当退出while循环时，temp就指向了链表的最后 //形成一个双向链表 temp.next = heroNode; heroNode.pre = temp; } //修改思路和单链表一样 public void update1(HeroNode2 heroNode2) { boolean flag = false; HeroNode2 temp = head.next; while (true) { //寻找要修改的结点 if (temp == null) { break; } else if (temp.number == heroNode2.number) { flag = true; break; } temp = temp.next; } if (flag) { temp.next = heroNode2.next; temp.pre = heroNode2.pre; } } public void update(HeroNode2 heroNode) { HeroNode2 temp = head.next; boolean flag = false; while (true) { if (temp.next == null) { break; } //匹配节点 if (temp.number == heroNode.number) { flag = true; break; } temp = temp.next; } if (flag) { temp.name = heroNode.name; temp.nextname = heroNode.nextname; } else { System.out.println("没有找到编号为" + heroNode.number + ""); } } //删除节点 //双向链表找到后可以自我删除不必借助其他结点 public void delete(int number) { HeroNode2 temp = head.next; boolean flag = false; //是否找到 while (true) { if (temp.next == null) { //到最后了 break; } if (temp.number == number) { flag = true; break; } temp = temp.next; //temp后移，遍历链表 } //被删除的结点，不会有其他引用指向，会被垃圾回收机制回收 //这和c语言一模一样啊！ if (flag) {// temp.next = temp.next.next; temp.pre.next = temp.next; //如果是最后一个节点，不需要执行下面这句话，否则会出现空指针 if (temp.next != null) { temp.next.pre = temp.pre; } else { System.out.println("没有找到要删除的结点" + number + "!"); } } }}class HeroNode2 { public int number; public String name; public String nextname; public HeroNode2 next; //指向下一个节点 public HeroNode2 pre;//指向前一个结点，默认为null public HeroNode2(int number, String name, String nextname) { this.number = number; this.name = name; this.nextname = nextname; } @Override public String toString() { return "HeroNode2{" + "number=" + number + ", name='" + name + '\'' + ", nextname='" + nextname + '\'' + '}'; }} 1 输出结果为： HeroNode2{number=1, name='宋江', nextname='及时雨'}HeroNode2{number=2, name='卢俊义', nextname='玉麒麟'}HeroNode2{number=3, name='吴用', nextname='智多星'}修改后的情况为HeroNode2{number=1, name='宋江', nextname='及时雨'}HeroNode2{number=2, name='BB', nextname='CC'}HeroNode2{number=3, name='吴用', nextname='智多星'} 1 循环链表 将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表（ circuar linkedlist)。 其实循环链表和单链表的主要差异就在于循环的判断条件上，原来是判断p->next是否为空，现在则是p-> next不等于头结点，则循环未结束。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XcoFO05D-1639655004233)(C:/Users/Jack/AppData/Roaming/Typora/typora-user-images/image-20211216110539595.png)]
约瑟夫环问题
约瑟夫问题是个有名的问题：N个人围成一圈，**从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。**例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3。
环行链表的思路分析：
构建一个单向的环形链表思路
1.先创建第一个节点,让first指向该节点,并形成环形
2.后面当我们每创建一个新的节点，就把该节点，加入到已有的环形链表中即可.
遍历环形链表
1.先让一个辅助指针(变量) curBoy，指向first节点
2.然后通过一个while循环遍历该环形链表即可curBoy.next == first结束
起始
curBoy.next -> newNode
boy.next -> first
curBoy = newNode
约瑟夫环思路分析：
