[数据结构与算法]2021-09-06

合并两个有序列表，合并后依然有序

public class Test {
    // 合并两个有序的单链表，合并之后的链表依然有序，
    public static void main(String[] args) {
    	// 第一个有序链表：新建节点和将节点有序添加进入链表
        CatNode cat1 = new CatNode(12,"白猫","小白猫");
        CatNode cat2 = new CatNode(10,"黑猫","小黑猫");
        CatNode cat3 = new CatNode(20,"灰猫","小灰猫");
        CatNode cat4 = new CatNode(40,"花猫","小花猫");
        LinkedList lins = new LinkedList();
        lins.addSort(cat4);
        lins.addSort(cat3);
        lins.addSort(cat1);
        lins.addSort(cat2);
		// 第二个有序链表：新建节点和将节点有序添加进入链表
        CatNode cat5 = new CatNode(8,"波斯猫","小白猫");
        CatNode cat6 = new CatNode(14,"梨花猫","小黑猫");
        CatNode cat7 = new CatNode(90,"短毛猫","小灰猫");
        CatNode cat8 = new CatNode(56,"尖嘴猫","小花猫");
        LinkedList lins2 = new LinkedList();
        lins2.addSort(cat8);
        lins2.addSort(cat5);
        lins2.addSort(cat7);
        lins2.addSort(cat6);


        // 合并链表
        System.out.println("合并后的链表");
        merge(lins,lins2).list();
    }

// 合并链表的方法，返回值为一个单链表
public static LinkedList merge(LinkedList l1, LinkedList l2){
	// 新建一个链表
	LinkedList preHead = new LinjedList();
	// 辅助指针
	CatNode prev = preHead.cHead;
	// 取出要合并链表的指针
	CatNode temp1 = l1.cHead.next;
	CatNode temp2 = l2.cHead.next;
	// 开始合并
	while(temp1 != null && temp2 != null){
			if(temp1.no <= temp2.no){
				prev.next = temp1;
				temp1 = temp1.next;
			}else {
			prev.next = temp2;
			temp2 = temp2.next;
			}
			// 辅助节点向后移动
			prev = prev.next;
		}
		// 代码走到这里说明有一个链表为空了，prev.next = temp1：将preHead链表的最后一个节点的next属性=temp1，如果temp1 == null，成立，则说明temp2还有节点，而且都比temp1的节点大，直接将tmep2的内存地址赋值给prev.next.
		prev.next = temp1 == null ? temp2 : temp1;
		return preHead;
	}
}


// 链表：链表中有将节点按编号升序排序的方法和遍历查看节点的方法
class LinkedList{
    // 创建一个头节点
    CatNode cHead = new CatNode(0,"","");

    // 按编号顺序增加
    public void addSort(CatNode catNode){
        CatNode temp = cHead;

        // true：有相同数据不能输入，false：没有相同节点
        boolean flage  = false;

        // 循环遍历
        while(true){
            if(temp.next == null){   // 说明已经是最后一个节点了
                break;
            }
            if(temp.next.no > catNode.no){  // 如果此时节点的下一个节点的编号大于要插入的节点，则表示找到要插入的位置了
                break;
            }else if(temp.next.no == catNode.no){   // 有相同编号，表示有重复数据
                flage = true;
                break;
            }
            // 以上条件都没有成立，表示此时节点的下一个节点编号比要插入的节点小，遍历下一个节点
            temp = temp.next;
        }
        if(flage){    // 为true
            System.out.println("编号为" + catNode.no + "在链表中已存在，无法插入");
        }else {
            // 插入数据
            catNode.next = temp.next;
            temp.next = catNode;
        }
    }

    // 遍历单向链表
    public void list(){
        if (cHead.next == null){
            System.out.println("链表为空无法遍历");
            return;
        }
        CatNode temp = cHead.next;
        while(true){
            if(temp == null){   // 已经是链表最后一个元素
                break;
            }
            // 输出节点
            System.out.println(temp);
            // 下一个节点
            temp = temp.next;
        }
    }
}

// 节点类
class CatNode{
    int no;
    String name;
    String nickName;
    CatNode next;

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

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

这种方式虽然效率没有递归高，但是便于理解。小白学韩顺平老师数据结构，有错误请各位大佬指出。