import java.util.Stack;
/**
* 单向链表CURD
*/
public class SingleLinkedListDemo {
public static void main(String[] args) {
// 测试
// 先创建节点
HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
HeroNode hero4 = new HeroNode(4, "公孙胜", "入云龙");
// 创建单向链表
SingleLinkedList singleLinkedList = new SingleLinkedList();
singleLinkedList.addByOrder(hero1);
singleLinkedList.addByOrder(hero2);
singleLinkedList.addByOrder(hero3);
singleLinkedList.addByOrder(hero4);
// 显示数据
singleLinkedList.list();
System.out.println("-------------------------------");
HeroNode herou = new HeroNode(2, "俊义", "玉麒麟");
singleLinkedList.update(herou);
singleLinkedList.list();
System.out.println("-------------------------------");
singleLinkedList.delete(4);
// singleLinkedList.delete(3);
// singleLinkedList.delete(2);
// singleLinkedList.delete(1);
singleLinkedList.list();
}
}
/**
* 单向链表
* 说明:链表的各个节点不一定是连续的(链式存储)
*/
class SingleLinkedList {
// 先初始化头节点,头节点不要动,不存放具体的数据
public HeroNode head = new HeroNode(0, "", "");
/**
* 添加节点到单向链表(直接加到尾部)
*
* @param heroNode
*/
public void add(HeroNode heroNode) {
// head不能动,需要一个辅助遍历temp
HeroNode temp = head;
while (temp.next != null) {
temp = temp.next;
}
// 循环结束,temp到达尾部,将下一个节点设为传入的参数
temp.next = heroNode;
}
/**
* 按照编号顺序插入
*
* @param heroNode
*/
public void addByOrder(HeroNode heroNode) {
// head不能动,需要一个辅助遍历temp
HeroNode temp = head;
boolean flag = false; // 标识添加的编号是否存在,默认为false
while (true) {
if (temp.next == null) { // 边界条件独立处理
break;
}
if (temp.next.no > heroNode.no) { // temp后面插入
break;
} else if (temp.next.no == heroNode.no) { // 已经存在,无法加入
flag = true;
break;
}
temp = temp.next; // 移动指针
}
if (flag) { // 无法插入
System.out.println("无法插入~");
} else {
heroNode.next = temp.next;
temp.next = heroNode;
}
}
/**
* 修改节点数据
*
* @param heroNode
*/
public void update(HeroNode heroNode) {
if (head.next == null) { // 空链表
System.out.println("链表为空~");
return;
}
// 定义辅助变量,存储头节点
HeroNode temp = head;
boolean flag = false;
while (true) {
if (temp.next == 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.println("未找到需修改的数据~");
}
/**
* 删除节点
*
* @param no
*/
public void delete(int no) {
HeroNode temp = head;
boolean flag = false; // 标志是否找到待删除节点
while (true) {
if (temp.next == null)
break;
if (temp.next.no == no) { // 找到待删除节点的前一个节点temp
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
temp.next = temp.next.next; // 跨越待删除的数据,待删除的数据会被JVM回收
} else
System.out.println("待删除的节点不存在~");
}
/**
* 显示链表
*/
public void list() {
if (head.next == null) {
System.out.println("链表为空~");
return;
}
// 记录头节点
HeroNode temp = head.next; // 头结点指示,实际数据从head.next开始
while (temp != null) { // 到达尾部
System.out.println(temp); // 输出数据
temp = temp.next; // 指针后移
}
}
/**
* 链表长度
*
* @param heroNode
* @return
*/
public static int getLength(HeroNode heroNode) {
if (heroNode.next == null) { // 静态方法中调用静态变量
return 0;
}
int length = 0;
HeroNode temp = heroNode;
while (temp.next != null) {
length++;
temp = temp.next;
}
return length;
}
/**
* 获取链表倒数第k个节点
*
* @param k
* @return
*/
public static HeroNode queryLastIndexNode(HeroNode heroNode, int k) {
if (heroNode.next == null) {
return null;
}
int size = getLength(heroNode); // size - k
// 校验k
if (k <= 0 || k > size) {
return null;
}
HeroNode temp = heroNode;
for (int i = 0; i < (size - k); i++) {
temp = temp.next;
}
return temp.next;
}
/**
* 反转链表
*
* @param heroNode
* @return
*/
public HeroNode reverseLinkedList(HeroNode heroNode) {
if (heroNode.next == null || heroNode.next.next == null) {
return heroNode; // 链表不变
}
// 定义一个辅助的指针,帮助遍历链表
HeroNode temp = heroNode.next;
HeroNode next = null; // 指向当前节点(temp)的下一个节点
HeroNode reverseHead = new HeroNode(0, "", "");
// 遍历原来的链表,每遍历一个链表,就将其取出,并放在新的链表reverseHead的最前端
while (temp != null) {
next = temp.next; // 存储当前节点的下一节点
temp.next = reverseHead.next; // 将temp的下一个节点指向新链表reverseHead的最前端
reverseHead.next = temp; // 将temp连接到新的链表上
temp = next; // 最后移动指针
}
heroNode.next = reverseHead.next;
return heroNode;
}
/**
* 倒序打印单链表
* 方法1:反转链表再遍历(破坏原链表结构)
* 方法2:栈实现
*
* @param heroNode
*/
public void reversePrintLinkedList(HeroNode heroNode) {
if (heroNode.next == null) {
return;
}
Stack<HeroNode> stack = new Stack<HeroNode>();
HeroNode temp = heroNode.next;
while (temp != null) {
stack.push(temp); // 入栈
temp = temp.next;
}
while (stack.size() > 0) {
System.out.println(stack.pop()); // 出栈
}
}
/**
* 合并两个有序链表(升序)
*
* @param heroNode1
* @param heroNode2
* @return
*/
public HeroNode mergeLinkedList(HeroNode heroNode1, HeroNode heroNode2) {
if (heroNode1 == null) {
return heroNode2;
}
if (heroNode2 == null) {
return heroNode1;
}
SingleLinkedList singleLinkedList = new SingleLinkedList(); // 用于操作链表
while (heroNode1 != null && heroNode2 != null) {
if (heroNode1.no > heroNode2.no) {
singleLinkedList.add(heroNode2); // 添加到全局变量head中
heroNode2 = heroNode2.next;
} else {
singleLinkedList.add(heroNode1); // 添加到全局变量head中
heroNode1 = heroNode1.next;
}
}
while (heroNode1 == null) {
singleLinkedList.add(heroNode2);
heroNode2 = heroNode2.next;
}
while (heroNode2 == null) {
singleLinkedList.add(heroNode1);
heroNode1 = heroNode1.next;
}
return head;
}
}
/**
* 定义HeroNode,每个HeroNode对象就是一个节点
*/
class HeroNode {
public int no;
public String name;
public String nickname;
public HeroNode next; // 指向下一个节点(为null时为链表尾部)
/**
* 构造方法
*
* @param no 编号
* @param name 姓名
* @param nickname 昵称
*/
public HeroNode(int no, String name, String nickname) {
this.no = no;
this.name = name;
this.nickname = nickname;
}
/**
* 重写toString()方法为了显示
*
* @return
*/
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
", nickname='" + nickname + '\'' +
'}';
}
}