剑指Offer （十六）：合并两个有序链表（Java版）

对于两个有序的链表，如下图，合并为一个更大的有序链表，如下图,那我们应该如何来实现呢？

{1,2,3,4}   {1,2,3,4}    合并以后 {1,1,2,2,3,3,4,4}

首先第一种方式也是最简单的一种方式，那就是采用递归的方式，判断两个链表的当前节点谁大谁小，将小的那个节点赋值给需要合并的链表，然后移动到较小链表的下一个节点，依次递归即可，代码如下

public static ListNode firstMerge(ListNode<Integer> list1,ListNode<Integer> list2) {
    if(null == list1 && null == list2){
        return null;
    }
    if( null == list1){
        return list2;
    }
    if(null == list2){


        return list1;
    }
    ListNode mergeHead = null;
    if(list1.val > list2.val){
        mergeHead = list2;
        mergeHead.next = firstMerge(list1,list2.next);
    }else {
        mergeHead = list1;
        mergeHead.next = firstMerge(list1.next,list2);
    }
    return mergeHead;
}

第二种方式，首先初始化一个链表，用于保存需要合并之后链表的头节点（不需要循环，经过一个if判断便可以确定两个链表中的最小值）。然后依次循环遍历两个有序链表，每次都指向当前节点数值小的节点即可，代码如下。

public static ListNode secondMerge(ListNode<Integer> list1,ListNode<Integer> list2) {
    if(null == list1 && null == list2){
        return null;
    }
    if( null == list1){
        return list2;
    }
    if(null == list2){
        return list1;
    }
    ListNode mergeHead = null;
    if(list1.val > list2.val){
        mergeHead = list2;
        list2 = list2.next;
    }else {
        mergeHead = list1;
        list1 = list1.next;
    }
    //用于遍历后续指针
    ListNode nextNode = mergeHead;
    while (null != list1 && null != list2){
        if(list1.val > list2.val){
            nextNode.next = list2;
            list2 = list2.next;
        }else {
            nextNode.next = list1;
            list1 = list1.next;
        }
        nextNode = nextNode.next;
    }


    //循环遍历以后，最多只有一个链表还没遍历完，加在链表的最后面即可。
    nextNode.next = null != list1 ? list1 : list2;
    return mergeHead;
}

完整代码如下

public class MainMergeListNode {

    public static void main(String[] args) {
        ListNode listNode0 = new ListNode(1);
        ListNode listNode1 = new ListNode(2);
        ListNode listNode2 = new ListNode(3);
        ListNode listNode3 = new ListNode(4);
        listNode0.next = listNode1;
        listNode1.next = listNode2;
        listNode2.next = listNode3;



        ListNode listNode4 = new ListNode(6);
        ListNode listNode5 = new ListNode(7);
        ListNode listNode6 = new ListNode(8);
        ListNode listNode7 = new ListNode(9);
        listNode4.next = listNode5;
        listNode5.next = listNode6;
        listNode6.next = listNode7;

        ListNode merge = secondMerge(listNode0, listNode4);
        System.out.println(merge.toString());

    }

    /**
     * 第一种通过递归方式实现
     * @param list1
     * @param list2
     * @return
     */
    public static ListNode firstMerge(ListNode<Integer> list1,ListNode<Integer> list2) {
        if(null == list1 && null == list2){
            return null;
        }
        if( null == list1){
            return list2;
        }
        if(null == list2){

            return list1;
        }
        ListNode mergeHead = null;
        if(list1.val > list2.val){
            mergeHead = list2;
            mergeHead.next = firstMerge(list1,list2.next);
        }else {
            mergeHead = list1;
            mergeHead.next = firstMerge(list1.next,list2);
        }
        return mergeHead;
    }

    public static ListNode secondMerge(ListNode<Integer> list1,ListNode<Integer> list2) {
        if(null == list1 && null == list2){
            return null;
        }
        if( null == list1){
            return list2;
        }
        if(null == list2){
            return list1;
        }
        ListNode mergeHead = null;
        if(list1.val > list2.val){
            mergeHead = list2;
            list2 = list2.next;
        }else {
            mergeHead = list1;
            list1 = list1.next;
        }
        //用于遍历后续指针
        ListNode nextNode = mergeHead;
        while (null != list1 && null != list2){
            if(list1.val > list2.val){
                nextNode.next = list2;
                list2 = list2.next;
            }else {
                nextNode.next = list1;
                list1 = list1.next;
            }
            nextNode = nextNode.next;
        }

        //循环遍历以后，最多只有一个链表还没遍历完，加在链表的最后面即可。
        nextNode.next = null != list1 ? list1 : list2;
        return mergeHead;
    }

}

最后

以上就是漂亮诺言为你收集整理的剑指Offer （十六）：合并两个有序链表（Java版）的全部内容，希望文章能够帮你解决剑指Offer （十六）：合并两个有序链表（Java版）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。