合并两个有序的单链表，合并之后依然有序

有问题或不满意请随时联系我

测试类

public class SinglelinkedListDemo {

    public static void main(String[] args) {
        //创建节点
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(6, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(8, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(10, "林冲", "豹子头");
        SinglelinkedList singlelinkedList = new SinglelinkedList();
        singlelinkedList.addByOrder(hero4);
        singlelinkedList.addByOrder(hero2);
        singlelinkedList.addByOrder(hero1);
        singlelinkedList.addByOrder(hero3);

        HeroNode animal1 = new HeroNode(2, "牛魔王", "牛头");
        HeroNode animal2 = new HeroNode(4, "孙悟空", "猴子");
        HeroNode animal3 = new HeroNode(7, "庄周", "鱼");
        HeroNode animal4 = new HeroNode(9, "瑶", "混子");
        SinglelinkedList singlelinkedList2 = new SinglelinkedList();
        singlelinkedList2.addByOrder(animal1);
        singlelinkedList2.addByOrder(animal2);
        singlelinkedList2.addByOrder(animal3);
        singlelinkedList2.addByOrder(animal4);

        System.out.println("链表1：");
        singlelinkedList.list();
        System.out.println("链表2：");
        singlelinkedList2.list();
        System.out.println("合并之后：");
        SinglelinkedList list = merge(singlelinkedList.getHead(), 		 singlelinkedList2.getHead());
        list.list();
    }


    //合并两个有序的单链表，合并之后依然有序
    public static SinglelinkedList merge(HeroNode head1, HeroNode head2){
        //创建一个新链表，用来存储合并之后的数据
        SinglelinkedList mergelinkedList = new SinglelinkedList();
        HeroNode mergelink = mergelinkedList.getHead();
        HeroNode cur1 = head1.next;
        HeroNode cur2 = head2.next;
        //判断链表为空值的情况
        if (head1.next == null || head2.next == null){
            if (head1 == null){
                mergelink.next = head2.next;
            }else {
                //head1不为空则head2必为空
                mergelink.next = head1.next;
            }
            return mergelinkedList;
        }
        //判断连个链表的第一个节点的值那个更小
        while(true){
            //链表不等时，当一个链表遍历完成之后，直接就可以进行判断了
            if (cur1 == null && cur2 != null){
                mergelink.next = cur2;
                break;
            }
            if (cur2 == null && cur1 != null){
                mergelink.next = cur1;
                break;
            }
            //对链表的大小进行比较
            if (cur1.getNo() < cur2.getNo() || cur1.getNo() == cur2.getNo()){
                mergelink.next = cur1;
                mergelink = mergelink.next;
                cur1 = cur1.next;
            }else {
                mergelink.next = cur2;
                mergelink = mergelink.next;
                cur2 = cur2.next;
            }
        }
        return mergelinkedList;
    }
}

链表类

public class SinglelinkedList {

    //初始化一个头节点，头节点不能发生变化,不存放具体的数据
    private HeroNode head = new HeroNode(0,"","");

    //返回头节点
    public HeroNode getHead() {
        return head;
    }

   public void addByOrder(@NotNull HeroNode heroNode){
        //由于头结点不能动，创建一个临时变量
        HeroNode temp = head;
        boolean flag = false;
        //获取所添加节点的序号
        int addNo = heroNode.getNo();
        //遍历链表进行数据比较
        while(true){
            if (temp.next == null){
                //若链表到达最后，直接添加
                break;
            }
            //若列表不为空，获取插入列表的位置
            if (temp.next.getNo() > addNo){//获取到需要插入的节点的位置
                break;
            }else if (temp.next.getNo() == addNo){
                flag = true;//说明编号存在
                break;
            }
            temp = temp.next;
        }
        if (flag){
            System.out.println("准备插入的英雄编号已经存在，不能添加编号为" + heroNode.getNo() + "的英雄");
        }else {
            //插入节点到链表中
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    //显示链表
    public void list(){
        //判断链表是否为空
        if (head.next == null){
            System.out.println("链表为空");
            return;
        }
        //链表不为空，由于头结点不能动，因此我们需要一个辅助变量来遍历
        HeroNode temp = head.next;
        while (true){
            if (temp == null){
                break;
            }else {
                System.out.println(temp);
                //将next后移
                temp = temp.next;
            }
        }
    }

}

实体类对象

public class HeroNode {

    public int  no;
    public String name;
    public String nickName;//指向下一个节点
    public HeroNode next;

    public HeroNode(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getNickName() {
        return nickName;
    }

    public void setNickName(String nickName) {
        this.nickName = nickName;
    }

    public HeroNode getNext() {
        return next;
    }

    public void setNext(HeroNode next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + ''' +
                ", nickName='" + nickName +
                '}';
    }
}