双向链表
package linkedlist;public class DooubleLinkedListDemo { public static void main(String[] args) { HeroNode2 hero1 = new HeroNode2(1,"宋江","及时雨"); HeroNode2 hero2 = new HeroNode2(2,"卢俊义","玉麒麟"); HeroNode2 hero3 = new HeroNode2(3,"吴用","智多星"); HeroNode2 hero4 = new HeroNode2(4,"林冲","豹子头"); DoubleLinkeList dll = new DoubleLinkeList();// dll.add(hero1);// dll.add(hero2);// dll.add(hero3);// dll.add(hero4);// dll.list();// HeroNode2 hero5 = new HeroNode2(4,"零充","豹子头");// dll.update(hero5);// dll.list();// dll.del(3); dll.addByOrder(hero1); dll.addByOrder(hero2); dll.list(); }}//创建一个双向链表的类class DoubleLinkeList{ //初始化一个头结点 private HeroNode2 head = new HeroNode2(0,"",""); public HeroNode2 getHead() { return head; } //遍历双向链表的方法 public void list() { if(head.next == null) { System.out.println("链表为null"); 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.next; } temp.next = heroNode; heroNode.pre=temp; } //有序添加 public void addByOrder(HeroNode2 heroNode) { HeroNode2 temp = head;//临时变量 boolean flag = false;//英雄没有存在就添加 while(true) { if(temp.next == null) { break; } if(temp.next.no>heroNode.no) { break; }else if(temp.next.no == heroNode.no) { flag = true; break; } temp = temp.next; } if(flag) { System.out.println("编号已经存在"); }else { temp.next=heroNode; heroNode.pre=temp; } } //修改节点的内容 public void update(HeroNode2 newHeroNode) { if(head.next == null) { System.out.println("链表为空"); return; } //定义辅助变量 HeroNode2 temp = head.next; boolean flag = false; while(true) { if(temp == null) { break; } if(temp.no == newHeroNode.no) { flag = true; break; } temp = temp.next; } if(flag) { temp.name = newHeroNode.name; temp.nickname = newHeroNode.nickname; }else { System.out.println("没有找到要修改的编号"); } } //删除节点 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) { flag = true; break; } temp = temp.next; } if(flag) { temp.pre.next = temp.next; if(temp.next != null ) { temp.next.pre = temp.pre; } }else { System.out.println("没有找到要删除的节点"); } } }//定义HeroNode,每个HeroNode 对象就是一个节点class HeroNode2{ public int no; public String name; public String nickname; public HeroNode2 next;//指向下一个节点 public HeroNode2 pre;//指向上一个节点 //构造器 public HeroNode2(int no, String name ,String nickname) { this.no = no; this.name = name; this.nickname = nickname; } @Override public String toString() { return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]"; }} 约瑟夫问题
package linkedlist;public class Josephu { public static void main(String[] args) { CircleSingleLinkedList csll = new CircleSingleLinkedList(); csll.addBoy(5); csll.showBoy(); csll.countBoy(1, 2, 5); }}//创建一个环形单向链表class CircleSingleLinkedList{ //创建一个first节点，当前没有编号 private Boy first = null; //添加小孩节点，构建成一个环形的链表 public void addBoy(int nums) { //nums 做一个数据校验 if(nums < 1) { System.out.println("nums的值不正确"); return; } Boy curBoy = null;//辅助指针,帮助构建环形链表 //使用for循环创建我们环形链表 for(int i=1; i<=nums; i++) { //根据编号，创建小孩节点 Boy boy = new Boy(i); //如果是第一个小孩 if(i == 1) { first =boy; first.setNext(first);//构成环装 curBoy = first;//让curBoy指向第一个小孩 }else { curBoy.setNext(boy); boy.setNext(first); curBoy = boy; } } } //遍历 public void showBoy() { if(first.getNext() == null) { System.out.println("链表为空"); return; } Boy curBoy = first; while(true){ System.out.println(curBoy.getNo()); if(curBoy.getNext() == first) { break; } curBoy = curBoy.getNext(); } } //根据用户输入，计算出小孩的出圈顺序 //startNo 表示从第几个小孩开始数数 //countNum 表示数几下 //nums 表示最初由多少个小孩在圈中 public void countBoy(int startNo,int countNum,int nums) { if(first == null || startNo <1 || startNo>nums) { System.out.println("参数输入有误"); return; } //创建辅助指针，帮助完成小孩出圈 Boy helper = first; //需求创建一个辅助指针helper,事先应该指向环形链表的最后这个节点 while(true) { if(helper.getNext() == first) { break; } helper = helper.getNext(); } for(int j=0;j