单链表
public class SingleLinkedListDemo {
public static void main(String[] args) {
// TODO Auto-generated method stub
// 开始测试
HeroNode hero1 = new HeroNode(1, "亚索", "疾风剑豪");
HeroNode hero2 = new HeroNode(2, "易", "无极剑圣");
HeroNode hero3 = new HeroNode(3, "菲奥娜", "无双剑姬");
HeroNode hero4 = new HeroNode(4, "阿托", "暗裔剑魔");
// 创建单链表
SingleLinkedList list = new SingleLinkedList();
// list.add(hero1);
// list.add(hero2);
// list.add(hero3);
// list.add(hero4);
// System.out.println("普通 插入……");
// list.list();
// 按顺序添加
list.addByNo(hero2);
list.addByNo(hero4);
list.addByNo(hero3);
list.addByNo(hero2);
list.addByNo(hero1);
// 按排序插入完打印下
System.out.println("orderbyno 插入……");
list.list();
// 测试修改
HeroNode hero5 = new HeroNode(4, "亚托克斯", "光明使者");
list.update(hero5);
System.out.println("修改完的链表");
list.list();
// 测试删除
list.del(2);
list.del(4);
System.out.println("删除完的链表");
list.list();
// 测试链表中的有效个数
System.out.println(list.getLength(list.getHead()));
// 测试是否查找到单链表中倒数第k个节点
System.out.println(list.getLastIndexNode(list.getHead(),4));
// 测试单链表的反转
list.reverse(list.getHead());
System.out.println("反转后的链表");
list.list();
// 测试从尾到头打印单链表
System.out.println("从尾到头……");
list.reverseList(list.getHead());
// 测试合并两个有序链表
SingleLinkedList list2 = new SingleLinkedList();
list2.addByNo(hero2);
list2.addByNo(hero4);
list.reverse(list.getHead());
System.out.println("打印list1");
list.list();
System.out.println("打印list2");
list2.list();
System.out.println("打印合并后的链表");
System.out.println(list.mergeTwoList(list.getHead(), list2.getHead()));
}
}
// 创建单链表但列表 管理英雄节点
class SingleLinkedList{
// 先定义一个头结点 头结点不要动 不存放具体的数据
HeroNode head = new HeroNode(0, "", "");
// 添加节点到单链表
// 思路：不考虑英雄排名顺序时
// 1、先找到当前链表的最后节点
// 2、将最后节点的next指向新的节点
public void add(HeroNode heroNode) {
// 定义一个临时节点 指向head;
HeroNode temp = head;
while (true) {
// 找到链表的最后一个节点位置
if (temp.next == null) {
break;
}
// 如果没有找到最后 将指针后移
temp = temp.next;
}
// 退出循环时即找到了当前链表的最后一个节点
// 将当前节点的next 指向新的节点
temp.next = heroNode;
}
// 添加节点到单链表
// 思路：考虑英雄排名顺序时
// 1、先找到要插入节点的前一个位置
// 2、heroNode.next = temp.next
// 3、temp.next = heroNode
public void addByNo(HeroNode heroNode) {
// 定义一个临时节点 指向head;
HeroNode 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) {
// 即找到了要插入节点的前一个位置
heroNode.next = temp.next;
temp.next = heroNode;
}else {
// 说明要插入的节点已经存在
System.out.printf("要插入的节点 %d 已存在，不能插入n",heroNode.no);
}
}
// 修改节点
// 思路：先判断找没找到要修改的节点
// 找到了让heroNode的name 和 nicename 赋值给当前节点
// 没找到就显示没有要修改的节点 无法修改
public void update(HeroNode heroNode) {
// 头结点不能动所以需要临时节点
HeroNode temp = head;
boolean flag = false;// 标志找没找到要修改的节点
while (true) {
// 链表空了
if (temp.next == null) {
break;
}
if (temp.next.no == heroNode.no) {
// 找到要修改的节点
flag = true;
break;
}
// 指针后移 遍历链表
temp = temp.next;
}
if (flag) {
// 找到了要修改的节点 开始修改
temp.next.name = heroNode.name;
temp.next.nickname = heroNode.nickname;
}else {
System.out.printf("要添加的节点%d不存在，无法修改n", heroNode.no);
}
}
// 删除链表
// 思路：先找到要删除链表的前一个位置 将temp.next = temp.next.next即删除
public void del(int no) {
// 老规矩 头结点不能动
HeroNode temp = head;
boolean flag = false;// 标志找没找到要删除的节点
while (true) {
// 链表空了
if (temp.next == null) {
break;
}
if (temp.next.no == no) {
// 找到要删除的节点了
flag = true;
break;
}
// 没找到就指针后移 遍历链表
temp = temp.next;
}
if (flag) {
// 找到了要删除的节点
temp.next = temp.next.next;
}else {
System.out.printf("要删除的节点%d不存在，无法删除", no);
}
}
// 打印链表
public void list() {
// 先判断当前链表是否为空
if (head == null) {
System.out.println("当前链表为空，没有数据呐，兄弟");
return;
}
// 定义一个临时变量辅助遍历
HeroNode temp = head.next;
while (true) {
// 判断是否到了最后
if(temp == null) {
break;
}
// 打印节点内容
System.out.println(temp.toString());
// 后移指针
temp = temp.next;
}
}
public int getLength(HeroNode head) {
//空链表
if (head == null || head.next == null) {
return 0;
}
// 头结点不计算
HeroNode cur = head.next;
int count = 0;
while(cur != null) {
count++;// 后移
cur = cur.next;
}
return count;
}
// 查找单链表中倒数第k个节点
public HeroNode getLastIndexNode(HeroNode head,int index) {
//空链表
if (head == null || head.next == null) {
return null;
}
HeroNode cur = head.next;
// 获得当前链表的有效个数
int count = getLength(head);
// 倒数index不存在
if (index < 0 || index > count) {
return null;
}
// 返回count - index 的节点
// count = 3 index = 1
for (int i = 0; i < count - index; i++) {
cur = cur.next;
}
return cur;
}
// 单链表的翻转
public void reverse(HeroNode head) {
// 链表为空或只有一个数据 不需要翻转 直接返回
if (head.next == null || head.next.next == null) {
return;
}
// 定义一个新链表
HeroNode newHead = new HeroNode(0, "", "");
// 辅助变量 帮助我们遍历
HeroNode cur = head.next;
// 定义一个next 指向当前cur的下一个节点
HeroNode next = null;
// 遍历当前链表 将遍历的节点取出 存放在newHead的最前面
while(cur != null) {
next = cur.next;// 存放当前节点的下一个节点
cur.next = newHead.next;// 将cur指向newHead的下一个节点
newHead.next = cur;// 将newHead的下一个节点指向cur 即遍历当前链表取出节点放在newHead的最前面
cur = next;// 后移
}
// 最后将head 指向newHead.next并返回 完成翻转
head.next = newHead.next;
}
// 从尾到头打印单链表
public void reverseList(HeroNode head) {
if (head == null || head.next == null) {
System.out.println("当前链表为空");
return;
}
// 使用栈
Stack stack = new Stack();
// 使用辅助变量 帮助遍历
HeroNode cur = head.next;
while(cur != null) {
stack.push(cur);// 遍历存入栈中
cur = cur.next;// 后移
}
// 开始出栈
while (stack.size() > 0) {
System.out.println(stack.pop());
}
}
// 合并两个有序链表
public HeroNode mergeTwoList(HeroNode node1,HeroNode node2) {
// 两个链表为空
if (node1.next == null && node2.next == null) {
return null;
}
// 定义一个新链表
HeroNode newHead = new HeroNode(0, "", "");
HeroNode prev = newHead;
// 遍历当前链表 将遍历的节点取出 存放在newHead的最前面
while (node1.next != null && node2.next != null) {
if (node1.next.no <= node2.next.no) {
prev.next = node1.next;
node1.next = node1.next.next;
}else {
prev.next = node2.next;
node2.next = node2.next.next;
}
prev = prev.next;
}
prev.next = node1.next == null?node2.next:node1.next;
return newHead.next;
}
public HeroNode getHead() {
return head;
}
public void setHead(HeroNode head) {
this.head = head;
}
}
// 先创建一个英雄节点
class HeroNode{
public int no;// 英雄编号
public String name;// 英雄名称
public String nickname;// 英雄昵称
public HeroNode next;
// 有参构造方法 alt + shift + s + o
public HeroNode(int no, String nameString, String nicknameString) {
this.no = no;
this.name = nameString;
this.nickname = nicknameString;
}
// tostring()
@Override
public String toString() {
return "HeroNode [no=" + no + ", nameString=" + name + ", nicknameString=" + nickname + next+"]";
}
}
双链表
public class DoubleLinkedListDemo {
public static void main(String[] args) {
// 开始测试
HeroNode2 hero1 = new HeroNode2(1, "亚索", "疾风剑豪");
HeroNode2 hero2 = new HeroNode2(2, "易", "无极剑圣");
HeroNode2 hero3 = new HeroNode2(4, "菲奥娜", "无双剑姬");
HeroNode2 hero4 = new HeroNode2(5, "阿托", "暗裔剑魔");
// 创建双向链表
DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
doubleLinkedList.add(hero1);
doubleLinkedList.add(hero2);
doubleLinkedList.add(hero3);
doubleLinkedList.add(hero4);
// // 打印双向链表
// doubleLinkedList.list();
// 测试按排名添加节点
// doubleLinkedList.addByNo(hero4);
// doubleLinkedList.addByNo(hero2);
// doubleLinkedList.addByNo(hero3);
// doubleLinkedList.addByNo(hero1);
// 打印双向链表
doubleLinkedList.list();
HeroNode2 hero5 = new HeroNode2(4, "亚托克斯", "光明使者");
// 测试修改
doubleLinkedList.update(hero5);
System.out.println("update ");
doubleLinkedList.list();
// 测试删除
doubleLinkedList.del(3);
System.out.println("del");
doubleLinkedList.list();
HeroNode2 hero6 = new HeroNode2(3, "小剑魔", "使者");
System.out.println("by order print");
doubleLinkedList.addByNo(hero6);
doubleLinkedList.list();
}
}
// 双向链表
class DoubleLinkedList{
HeroNode2 head = new HeroNode2(0,"", "");
public HeroNode2 getHead() {
return head;
}
// 添加节点到单链表
// 思路：不考虑英雄排名顺序时
// 1、先找到当前链表的最后节点
// 2、将最后节点的next指向新的节点
public void add(HeroNode2 heroNode) {
// 定义一个临时节点 指向head;
HeroNode2 temp = head;
while (true) {
// 找到链表的最后一个节点位置
if (temp.next == null) {
break;
}
// 如果没有找到最后 将指针后移
temp = temp.next;
}
// 退出循环时即找到了当前链表的最后一个节点
temp.next = heroNode;
heroNode.pre = temp;
}
// 添加节点到单链表
// 思路：考虑英雄排名顺序时
// 1、先找到要插入节点的前一个位置
// 2、heroNode.next = temp.next
// 3、temp.next = heroNode
public void addByNo(HeroNode2 heroNode) {
// 定义一个临时节点 指向head;
HeroNode2 temp = head;
boolean flag = false;// 标志要插入的节点是否已经存在 默认不存在
while (true) {
// 找到链表的最后一个节点位置
if (temp.next == null) {
break;
}
if (temp.no > heroNode.no) {// 找到要插入节点的前一个位置
break;
}else if (temp.no == heroNode.no) {
// 要插入的节点已经存在
flag = true;
break;
}
// 如果没有找到 将指针后移
temp = temp.next;
}
if (!flag) {
// 即找到了要插入节点的前一个位置
temp.pre.next = heroNode;
heroNode.next = temp;
heroNode.pre = temp.pre;
temp.pre = heroNode;
}else {
// 说明要插入的节点已经存在
System.out.printf("要插入的节点 %d 已存在，不能插入n",heroNode.no);
}
}
// 修改节点
// 思路：先判断找没找到要修改的节点
// 找到了让heroNode的name 和 nicename 赋值给当前节点
// 没找到就显示没有要修改的节点 无法修改
public void update(HeroNode2 heroNode) {
// 头结点不能动所以需要临时节点
HeroNode2 temp = head;
boolean flag = false;// 标志找没找到要修改的节点
while (true) {
// 链表空了
if (temp == null) {
break;
}
if (temp.no == heroNode.no) {
// 找到要修改的节点
flag = true;
break;
}
// 指针后移 遍历链表
temp = temp.next;
}
if (flag) {
// 找到了要修改的节点 开始修改
temp.name = heroNode.name;
temp.nickname = heroNode.nickname;
}else {
System.out.printf("要修改的节点%d不存在，无法修改n", heroNode.no);
}
}
// 删除链表
// 思路：先找到要删除链表的前一个位置 将temp.next = temp.next.next即删除
public void del(int no) {
if (head.next == null) {
System.out.println("链表为空无法删除");
return;
}
// 老规矩 头结点不能动
HeroNode2 temp = head;
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是否为链表尾部
temp.next.pre = temp.pre;
}else {
// 当前temp在链表尾部
temp.pre = null;
}
}else {
System.out.printf("要删除的节点%d不存在，无法删除", no);
}
}
// 打印链表
public void list() {
// 先判断当前链表是否为空
if (head == null) {
System.out.println("当前链表为空，没有数据呐，兄弟");
return;
}
// 定义一个临时变量辅助遍历
HeroNode2 temp = head.next;
while (true) {
// 判断是否到了最后
if(temp == null) {
break;
}
// 打印节点内容
System.out.println(temp.toString());
// 后移指针
temp = temp.next;
}
}
}
//先创建一个英雄节点
class HeroNode2{
public int no;// 英雄编号
public String name;// 英雄名称
public String nickname;// 英雄昵称
public HeroNode2 pre;// 前驱
public HeroNode2 next;// 后继
// 有参构造方法 alt + shift + s + o
public HeroNode2(int no, String nameString, String nicknameString) {
this.no = no;
this.name = nameString;
this.nickname = nicknameString;
}
// tostring()
@Override
public String toString() {
return "HeroNode [no=" + no + ", nameString=" + name + ", nicknameString=" + nickname +"]";
}
}
链表实际应用——约瑟夫环
// 吃小孩的约瑟夫问题
public class Josephu {
public static void main(String[] args) {
// TODO Auto-generated method stub
// 测试一下
CircleSingleLinkedList cList = new CircleSingleLinkedList();
cList.add(250);// 创建5个超可爱的小孩
// 打印他们
cList.list();
cList.getBoy(250, 1, 2);
}
}
// 单向环形链表
class CircleSingleLinkedList{
// 创建一个first结点 当前没有编号
Boy first = null;
// 添加小孩结点 创建环形链表
public void add(int nums) {
// nums做一个数据校验
if (nums < 1) {
System.out.println("你输入的小孩个数太少了 不够吃的啊");
return;
}
Boy curBoy = null;// 辅助指针，帮助构建环形链表
// 使用循环来建立环形链表
for (int i = 1; i <= nums; i++) {
// 根据编号 创建小孩
Boy boy = new Boy(i);
// 如果是第一个小孩
if (i == 1) {
first = boy;
first.setNext(boy);// 构成环
curBoy = first;// 让 curBoy指向第一个小孩
}else {
curBoy.setNext(boy);
boy.setNext(first);
curBoy = boy;
}
}
}
// 遍历环形链表
public void list() {
if (first == null) {
System.out.println("当前没有小孩可以吃 ");
return;
}
Boy curBoy = first;
while (true) {
System.out.printf("当前小孩编号%dn",curBoy.getNo());
if (curBoy.getNext() == first) {
// 说明遍历完了 退出
break;
}
curBoy = curBoy.getNext();
}
}
// 从第k哥小孩开始隔n个小孩报数 输出报数的小孩然后吃掉
public void getBoy(int nums,int k,int n) {
Boy helper = first;// 辅助指针 指向环形链表的最后节点
while (true) {
// 将helper指向当前链表最后一个结点
if (helper.getNext() == first) {
break;
}
helper = helper.getNext();
}
// 小孩报数前 让first 和 helper 移动 k-1
for (int i = 0; i < k - 1; i++) {
first = first.getNext();
helper = helper.getNext();
}
// 小孩报数时 让first 和 helper 移动 n-1
while (true) {
if (helper == first) {
// 链表里只有一个数据
break;
}
for (int i = 0; i < n - 1; i++) {
first = first.getNext();
helper = helper.getNext();
}
// 这时first指向的节点 就是要出圈的小孩节点
System.out.printf("出圈的小孩是%dn",first.getNo());
first = first.getNext();
helper.setNext(first);
}
System.out.printf("最后留在圈中的小孩编号%d n", first.getNo());
}
}
// 链表节点
class Boy{
private int no;
private Boy next;
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;
}
}
