java实现单链表以及 增加、合并、反转等功能
链表的结构很简单，就是一个个节点连接在一起，形成一个完整的链条，每个节点包含2部分，数据域，和一个指向下一个节点引用的指针next。
具体的代码实现
代码里面注释的很清楚了，也有应用于测试的main方法
public class LinkedListDemo {
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, "卢俊义", "玉麒麟");
LinkedList list = new LinkedList();
LinkedList list1 = new LinkedList();
LinkedList list2 = new LinkedList();
list1.addByOrder(hero1);
list2.addByOrder(hero4);
list1.addByOrder(hero3);
list2.addByOrder(hero2);
System.out.println("第一个链表中的数据");
list1.showLinkedList();
System.out.println("第二个链表中的数据");
list2.showLinkedList();
System.out.println("合并后链表中的数据");
HeroNode combinelist = combineList(list1.head.next, list2.head.next);
HeroNode print = new HeroNode();
print = combinelist;
while (print != null) {
System.out.println(print);
print = print.next;
}
System.out.println("将合并后的链表倒序输出");
reverPrint(combinelist);
System.out.println("将合并后的链表倒转后的链表");
HeroNode print1 = new HeroNode();
print1.next = combinelist;
reversetList(print1);
while (print1.next != null) {
System.out.println(print1.next);
print1 = print1.next;
}
}
/**
* 查询链表中 有效节点的个数
* 思路：
* 1.创建一个临时变量，记录有效节点你的个数
* 2.便利传进来的 链表
*
* @param head 传进来头节点
* @return 返回有效节点的个数
*/
private static int indexNode(HeroNode head) {
//判断链表是否为空
if (head.next == null) {
System.out.println("链表为空.");
return 0;
}
//如果链表不为空的话 对链表进行遍历
int num = 0;
//创建一个临时变量 用来遍历 操作
HeroNode term = head.next;
while (term != null) {
num++;
term = term.next;
}
return num;
}
/**
* 将节点 加入到链表中 指定节点的位置
* 思路：
* 1.首先判断传 进来的链表中 有效数据的 总个数
* 2.链表中有效数据的总个数 - index（倒数第index个节点） = 得到的结果是 需要返回第几个节点的信息
*
* @param head 传进去链表的头部
* @return 返回 链表中倒数第n个节点的信息
*/
private static HeroNode findIndexNode(HeroNode head, int index) {
//首先判断链表是否为空
if (head.next == null) {
System.out.println("链表为空。");
return null;
}
HeroNode term = head.next;
int max = indexNode(head);
if (max < index) {
System.out.println("有效数据个数小于 倒数节点的数目。");
return null;
}
for (int i = 0; i < max - index; ++i) {
term = term.next;
}
return term;
}
/**
* 将链表 反转 改变链表的结构
* 思路：
* 1.首先创建一个新的头节点
* 2.让后将传进来的链表的节点信息一个一个从头部插入进去 实现链表的反转
* 3.最后用传进来的头节点执向新的头节点
*
* @param head 传进去待 反转链表的头部
*/
private static void reversetList(HeroNode head) {
//判断链表是否回空 或者链表是否只有一个节点
if (head == null || head.next == null) {
return;
}
//创建新的链表头部
HeroNode newhead = new HeroNode(0, "", "");
HeroNode term = head.next;
HeroNode next = null;
while (term != null) {
next = term.next; //保存当前节点的下一个节点的信息
// 将链表 倒须， 就是将链表的 从第一个节点开始一个一个的将节点插入到链表的 第一个节点的位置
term.next = newhead.next; //将当前节点的下一个节点的地址更改为第一个节点的地址（如果当前term节点为第一个节点 那个这个节点操作后就会变成最后一个节点 所以第一个节点的下一个节点的信息为“”）
newhead.next = term; //将头节点指向的第一个节点的 信息更改为当前的term节点 实现节点的插入操作
term = next;
}
//让以前的头节点 指向这个新的链表
head.next = newhead.next;
}
/**
* 反向打印链表 不改变链表的结构
* 思路
* 第一种方法：将链表反转 让后打印（不推荐 因为将来链表过大 就太浪费时间了）
* 第二种方法：利用 栈 先进后出的原则，将链表反向打印
*/
private static void reverPrint(HeroNode head) {
//首先判断链表是否为空
if (head == null) {
System.out.println("链表为空");
return;
}
//创建一个栈
Stack<HeroNode> stack = new Stack<>();
//将 链表中节点的信息 加入到栈中 入栈操作
HeroNode item = head;
while (item != null) {
stack.push(item);
item = item.next;
}
//浆栈 中的元素取出来 出栈操作
while (stack.size() > 0) {
System.out.println(stack.pop());
}
}
/**
* 合并两个已知顺序的链表 按顺序合并
* 思路：
* 1.创建一个新的链表
* 2.将待合并的两个链表 按顺序 比较
* 3.将小的数据 加入到 新的链表中
*
* @param head1 第一个链表头部
* @param head2 第二个连表头部
* @return 返回合成后的链表
*/
private static HeroNode combineList(HeroNode head1, HeroNode head2) {
if (head1 == null && head2 == null) {
return null;
}
if (head1 == null) {
return head2;
} else if (head2 == null) {
return head1;
} else {
HeroNode temp = null;
if (head1.no > head2.no) {
temp = head2;
temp.next = combineList(head1, head2.next);
} else if (head1.no < head2.no) {
temp = head1;
temp.next = combineList(head1.next, head2);
}
return temp;
}
}
}
class LinkedList {
//一个空的 链表的头部
HeroNode head = new HeroNode(0, "", "");
public void addLinkedList(HeroNode hero) {
// 思路： 首先寻找链表的尾部 让后将数据插入进去
//链表的头部不可以动，所以需要一个临时变量，来寻找链表的尾部
HeroNode term = head;
//首先遍历整个链表 寻找链表的尾部
while (true) {
if (term.next == null) {
//将数据插入到链表的尾部
term.next = hero;
break;
}
term = term.next;
}
}
//在指定位置 添加节点
public void addByOrder(HeroNode hero) {
HeroNode temp = head;
while (true) {
if (temp.next == null) {
temp.next = hero;
break;
}
//条件满足就把节点 添加到后面
if (temp.next.no > hero.no) {
hero.next = temp.next;
temp.next = hero;
break;
} else if (temp.next.no == hero.no) {
System.out.println("节点" + hero.no + "已存在，添加失败");
break;
}
temp = temp.next;
}
}
//根据 节点的编号进行查找，让后修改
public void update(HeroNode hero) {
HeroNode temp = head;
while (true) {
if (temp.next == null) {
System.out.println("链表为空，修改失败！");
break;
}
if (temp.next.no == hero.no) {
temp.next.name = hero.name;
temp.next.nickname = hero.nickname;
break;
}
temp = temp.next;
}
}
//删除节点 根据编号进行删除节点，删除后的节点 idea的垃圾回收机制会进行回收
public void delet(HeroNode hero) {
HeroNode temp = head;
while (true) {
if (temp.next == null) {
System.out.println("链表为空，删除节点失败。");
break;
}
if (temp.next.no == hero.no) {
temp.next = temp.next.next;
break;
}
temp = temp.next;
}
}
public void showLinkedList() {
if (head.next == null) {
System.out.println("链表为空。");
return;
}
HeroNode term = head.next;
while (true) {
System.out.println(term);
term = term.next;
if (term == null) {
break;
}
}
}
}
class HeroNode {
public int no;
public String name;
public String nickname;
HeroNode next;
public HeroNode() {
}
HeroNode(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 + '\'' +
'}';
}
}运行结果截图
