Java练习-两链表相加

77 阅读 0 评论 51 点赞

我是靠谱客的博主潇洒小甜瓜，最近开发中收集的这篇文章主要介绍Java练习-两链表相加，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Java-两个有序单链表合并为新的链表

package A_1;
public class A_1_1 {
public static void main(String[] args) {
// TODO Auto-generated method stub
/*1.任务说明：
* 将两个单链表（顺序表）按大小合并成为一个单链表
*2.思路:
*分别创建两个单链表和对应的辅助指针
*第一位开始比较大小，小的先入，大的次之。（假设没有重复元素）
* */
//创建6个节点，奇数在链表1，偶数在链表2
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
Node node6 = new Node(6);
//创建两链表并填入数据
singlelinked linked1 = new singlelinked();
singlelinked linked2 = new singlelinked();
singlelinked linked3 = new singlelinked();
//调用函数向链表中添加数据并显示出来
linked1.addsinglelinked(node1);
linked1.addsinglelinked(node3);
linked1.addsinglelinked(node5);
System.out.println("第一个链表");
linked1.list();
linked2.addsinglelinked(node2);
linked2.addsinglelinked(node4);
linked2.addsinglelinked(node6);
System.out.println("第二个链表");
linked2.list();
//输入三链表头节点得到相加结果
addtosinglelinked(linked1.getHead(),linked2.getHead(),linked3.getHead());
System.out.println("合并后第三个链表");
linked3.list();
}
//3.将两链表按顺序添加进一个链表
public static Node addtosinglelinked(Node head1,Node head2,Node head3) {
Node temp1 = head1.next;	//定义第一个链表的辅助指针
Node temp2 = head2.next;	//定义第二一个链表的辅助指针
Node temp3 = head3;	//表示合链表（3链表）
if(head1.next == null) {
head3.next = head2.next;//若链表1为空，则3链表 = 链表2
}else if(head2.next == null) {
head3.next = head1.next;//2链表为空，3链表 = 1链表
}else if(head1.next == null&&head2.next == null) {
System.out.println("两个子链表为空，所以相加为空");
return null;
}
//没有子链表为空，开始比较两链表大小并加入3链表中
while(temp1 != null && temp2 != null) {
if(temp1.valu < temp2.valu) {
temp3.next = temp1;
temp1 = temp1.next;
}else {
temp3.next = temp2;
temp2 = temp2.next;
}
temp3 = temp3.next;
}
if(temp1==null) {
temp3.next = temp2;
}else if(temp2==null) {
temp3.next = temp1;
}
return head3;
}
}
/*创建链表类，实现创建链表*/
class singlelinked{
private Node head = new Node(0);	//创建头节点，不存任何信息
//重写方法带出头节点
public Node getHead() {
return head;
}
//1.创建添加方法，将节点分别添加进两个单链表中去
public void addsinglelinked(Node node) {
//找到最后节点，在其尾部添加新节点
Node temp = head;
while(true) {
if(temp.next == null) {
break;
}
temp = temp.next;
}
//运行到当前语句代表已经找到尾节点
temp.next = node;
//添加完毕
}
//2.显示链表内元素
public void list() {
if(head.next==null) {
System.out.println("链表为空~~~~");
return;
}
Node temp = head;
while(true) {
if(temp == null) {
break;
}
System.out.println(temp);
temp = temp.next;
}
}
}
/*创建节点类，定义链表中每一个节点*/
class Node{
public int valu;	//定义节点内容(整型数字)
public Node next;
// 指向下一节点
/*创建构造器，构造节点*/
public Node(int newvalu) {
this.valu = newvalu;
}
/*重新构造输出，toString*/
@Override
public String toString() {
return "Node [valu=" + valu + "]";
}
}