Java实现单链表的合并(保证数据的有序性)

一、思路

1.比较两个链表的大小
2.将小链表插入到大链表中
3.使用插入保证链表数据的有序性

二、核心代码

/**
* 合并两个链表，并且按照有序合并
* @param singleLinkedList1 链表1
* @param singleLinkedList2 链表2
*/
public static void mergeLinkedList2(SingleLinkedList singleLinkedList1, SingleLinkedList singleLinkedList2) {
int num1 = getLength(singleLinkedList1.getNode());
int num2 = getLength(singleLinkedList2.getNode());
if (singleLinkedList1.getNode().next == null || singleLinkedList2.getNode().next == null) {
return;
}
if (num1 >= num2) {
Node cur = singleLinkedList2.getNode().next;
Node cur2 = null;
while (cur != null) {
cur2 = cur.next;
singleLinkedList1.insert(cur);
cur = cur2;
}
} else {
Node temp = singleLinkedList1.getNode().next;
Node temp2 = null;
while (temp != null) {
temp2 = temp.next;
singleLinkedList2.insert(singleLinkedList1.getNode());
temp = temp2;
}
}
}

三、全代码

package com.company;


import java.util.Stack;

/**
* @author:抱着鱼睡觉的喵喵
* @date:2021/2/4
* @description:
*/
public class LinkedListDemo {
public static void main(String[] args) {
Node node4 = new Node(4, 96, "Ronin");
Node node1 = new Node(2, 100, "lisi");
Node node2 = new Node(1, 99, "张三");
Node node3 = new Node(3, 63, "zsh");
Node node5 = new Node(5, 65, "zms");


SingleLinkedList singleLinkedList = new SingleLinkedList();
SingleLinkedList singleLinkedList2 = new SingleLinkedList();

singleLinkedList.insert(node4);
singleLinkedList.insert(node1);
singleLinkedList.insert(node2);
singleLinkedList2.insert(node3);
singleLinkedList2.insert(node5);
mergeLinkedList2(singleLinkedList,singleLinkedList2);
int num1 = getLength(singleLinkedList.getNode());
int num2 = getLength(singleLinkedList2.getNode());
if (num1 >= num2) {
singleLinkedList.list();
} else {
singleLinkedList2.list();
}

}

//计算链表长度
public static int getLength(Node node) {
if (node.next == null) {
return 0;
}
int length = 0;
Node cur = node.next;
while (cur != null) {
length++;
cur = cur.next;
}
return length;
}


/**
* 合并两个链表，并且按照有序合并
* @param singleLinkedList1 链表1
* @param singleLinkedList2 链表2
*/
public static void mergeLinkedList2(SingleLinkedList singleLinkedList1, SingleLinkedList singleLinkedList2) {
int num1 = getLength(singleLinkedList1.getNode());
int num2 = getLength(singleLinkedList2.getNode());
if (singleLinkedList1.getNode().next == null || singleLinkedList2.getNode().next == null) {
return;
}
if (num1 >= num2) {
Node cur = singleLinkedList2.getNode().next;
Node cur2 = null;
while (cur != null) {
cur2 = cur.next;
singleLinkedList1.insert(cur);
cur = cur2;
}
} else {
Node temp = singleLinkedList1.getNode().next;
Node temp2 = null;
while (temp != null) {
temp2 = temp.next;
singleLinkedList2.insert(singleLinkedList1.getNode());
temp = temp2;
}
}
}
}

//节点类
class Node {
public Node next;
public int sno;
public int score;
public String data;


public Node() {
}

public Node(int Sno, int NScore, String Data) {
this.sno = Sno;
this.score = NScore;
this.data = Data;
}

@Override
public String toString() {
return "Node{" +
"sno=" + sno +
", score=" + score +
", data='" + data + '\'' +
'}';
}
}

//节点操作类
class SingleLinkedList {
private Node head = new Node(0, 0, ""); //初始化头节点

public Node getNode() {
return head;
}

// add student data
public void add(Node node) { //数据添加
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = node;
}

//output
public void list() { //遍历数据进行打印
Node temp = head.next;
if (temp == null) {
System.out.println("LinkedList is empty!");
} else {
while (temp != null) {
System.out.println(temp);
System.out.println();
temp = temp.next;
}
}

}


//insert by order 2

public void insert(Node node) { //插入数据方式2
Node temp = head;
boolean flag = false;
while (true) {
if (temp.next == null) {
break;
}
if (temp.next.sno > node.sno) {
break;
} else if (temp.next.sno == node.sno) {
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
System.out.println("Student ID ：" + node.sno + "already exists!");
return;
} else {
node.next = temp.next;
temp.next = node;
}
}

public void modify(Node newNode) { //修改操作
Node temp = head.next;
if (head.next == null) {
System.out.println("LinkedList is empty,unable to modify!");
return;
}
boolean flag = false;
while (true) {
if (temp == null) {
break;
}
if (temp.sno == newNode.sno) {
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
temp.score = newNode.score;
temp.data = newNode.data;
} else {
System.out.println("No student ID" + newNode.sno);
}
}

public void delete(int sno) { //删除操作
Node temp = head;
boolean flag = false;
if (head.next == null) {
System.out.println("LinkedList is empty,Unable to delete.");
return;
}
while (true) {
if (temp.next == null) {
break;
}
if (temp.next.sno == sno) {
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
temp.next = temp.next.next;
} else {
System.out.println("No student ID:" + sno);
}
}

}