java数据结构和算法——单链表（Linked List）合并两个单链表，合并之后的链表依然有序

一、合并两个单链表，合并之后的链表依然有序的代码示例

1、定义一个人员节点类，每一个PersonNode对象就是一个节点

package com.rf.springboot01.dataStructure.singleLinkedList2;
/**
 * @description: 定义一个人员节点类，每一个PersonNode对象就是一个节点
 * @author: xiaozhi
 * @create: 2020-07-15 16:44
 */
public class PersonNode {

    public int num;//编号
    public String name;//名称
    public String aliasName;//别名
    public PersonNode next;//指向下一个节点

    //构造器
    public PersonNode(int num, String name, String aliasName) {
        this.num = num;
        this.name = name;
        this.aliasName = aliasName;
    }
    public PersonNode() {

    }

    //重写toString方法
    @Override
    public String toString() {
        return "PersonNode{" +
                "num=" + num +
                ", name='" + name + '\'' +
                ", aliasName='" + aliasName + '\'' +
                '}';
    }
}

2、创建一个单链表管理人员节点

package com.rf.springboot01.dataStructure.singleLinkedList2;
/**
 * @description:
 * @author: xiaozhi
 * @create: 2020-07-21 23:26
 */
public class SingleLinkedList {
    //先初始化一个头结点，头节点位置固定，不存放任何数据，作用是表示链表的头节点
    private PersonNode head;

    public SingleLinkedList(PersonNode head) {
        this.head = head;
    }
    public SingleLinkedList() {
        head = new PersonNode();
    }

    //在链表的指定位置添加节点数据
    public void addByNum(PersonNode personNode) {
        PersonNode temp = head;
        boolean flag = false;//插入的编号是否存在，默认不存在
        while (true) {
            if (temp.next == null) {//已经在链表的尾部
                break;
            }
            if (temp.next.num > personNode.num) {//找到位置，在temp后添加
                break;
            }
            if (temp.next.num == personNode.num) {//编号已经存在，不能添加
                flag = true;
                break;
            }
            temp = temp.next;//后移，遍历
        }
        if (flag) {
            System.out.printf("添加的人员编号%d已经存在，不能添加\n", personNode.num);
        } else {
            //添加数据到链表中，temp后的位置
            personNode.next = temp.next;
            temp.next = personNode;
        }

    }

    //显示链表
    public void show() {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //因为头节点不能动，所以需要一个临时变量来遍历
        PersonNode temp = head.next;
        while (true) {
            //判断是否到链表最后
            if (temp == null) {
                break;
            }
            //输出节点信息
            System.out.println(temp);
            //将temp向后移动
            temp = temp.next;
        }
    }

    /**
     * @Description: 合并两个单链表，合并之后的链表依然有序
     * @Param: head1  head2
     * @Author: xz
     * @return: PersonNode
     * @Date: 2020/7/21 15:50
     */
    public static SingleLinkedList mergeLinkedList(SingleLinkedList list1, SingleLinkedList list2) {
        // 判断需要合并的链表是否为空
        if (list1.head.next == null && list2.head.next == null) {
            throw new RuntimeException("需要合并的两条链表都为空！");
        }
        // 一条链表为空，直接返回另一条链表
        if (list1.head.next == null) {
            System.out.println(list2);
        }
        if (list2.head.next == null) {
            System.out.println(list1);
        }
        //定义合并之后的新链表的头节点
        PersonNode newHead = new PersonNode();
        PersonNode current = newHead; // 定义一个current结点指向新链表
        //定义临时变量
        PersonNode temp1 = list1.head.next;
        PersonNode temp2 = list2.head.next;
        while (temp1 != null && temp2 != null) {
            if (temp1.num