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;}@Overridepublic 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 datapublic void add(Node node) {        //数据添加Node temp = head;while (temp.next != null) {temp = temp.next;}temp.next = node;}//outputpublic 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 2public void insert(Node node) {      //插入数据方式2Node 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);}}}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！