[数据结构与算法]两个有序单链表合并【面试题】

方式一

如果题目没有说不能破坏其中一个链表，则可以以其中一个链表为中心，依次取另外一个链表的元素，addByOrder加入第一个链表中

方式二

创建一个新链表

public static void main(String[] args) {

        HeroSingleLinkedList heroSingleLinkedList = new HeroSingleLinkedList();
        System.out.println("-------------以下是添加---------------");
        heroSingleLinkedList.addByOrder(new Hero(1,"宋江","及时雨"));
        heroSingleLinkedList.addByOrder(new Hero(9,"吴用","智多星"));
        heroSingleLinkedList.addByOrder(new Hero(5,"李逵","黑旋风"));
        heroSingleLinkedList.showHeros();

        HeroSingleLinkedList heroSingleLinkedList1 = new HeroSingleLinkedList();
        System.out.println("-------------以下是添加---------------");
        heroSingleLinkedList1.addByOrder(new Hero(2,"宋江1","及时雨1"));
        heroSingleLinkedList1.addByOrder(new Hero(6,"吴用1","智多星1"));
        heroSingleLinkedList1.addByOrder(new Hero(4,"李逵1","黑旋风1"));
        heroSingleLinkedList1.addByOrder(new Hero(3,"李逵3","黑旋风3"));
        heroSingleLinkedList1.showHeros();
        System.out.println("-------------以下是合成后的---------------");
        mergeTwoLinkedLists(heroSingleLinkedList,heroSingleLinkedList1).showHeros();

}
public static HeroSingleLinkedList mergeTwoLinkedLists(HeroSingleLinkedList first,HeroSingleLinkedList second){
        //创建一个新链表，用来保存最终的链表
        HeroSingleLinkedList finalLinkedList = new HeroSingleLinkedList();
        //分别创建指向两个旧链表的变量
        Hero curFirst = first.head.next;
        Hero curSecond = second.head.next;

        while (curFirst != null && curSecond != null){
            if (curFirst.num > curSecond.num){
                Hero curSecondNext = curSecond.next;
                curSecond.next = null;

                finalLinkedList.addHero(curSecond);
                curSecond = curSecondNext;
            }else if (curFirst.num <= curSecond.num){
                Hero curFirstNext = curFirst.next;
                curFirst.next = null;

                finalLinkedList.addHero(curFirst);
                curFirst = curFirstNext;
            }
        }

        //把最后剩下的那些加完
        if (curFirst == null){
            while (curSecond != null){
                //说明第一个已经加完了
                finalLinkedList.addHero(curSecond);
                curSecond = curSecond.next;
            }
        }else{
            while (curFirst != null){
                //说明第二个已经加完了
                finalLinkedList.addHero(curFirst);
                curFirst = curFirst.next;
            }
        }

        return finalLinkedList;
}

注意点①

在addHero的时候，需要把添加到新链表的hero对象的next赋为null，否则会将此hero对象和后面的所有对象都加进去。此时可以设置两个引用，一个指向当前元素，另一个指向下一元素，防止下一元素丢失。

注意点②

这里要用else if （或者else）而不是另外一个if，因为两者要走其中一个，走了一个另外一个就不要走了。