[数据结构与算法]leetcode21-合并两个有序链表

一.题目描述

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

输入：l1 = [], l2 = []
输出：[]

输入：l1 = [], l2 = [0]
输出：[0]

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

二.题目解析

public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        /*借鉴归并排序的合并过程的思想，双指针遍历，每次比较存取较小的值到新的链表节点中
        * */
        ListNode res = null;
        //建立虚拟头结点方便统一处理
        ListNode dummyHead = new ListNode(-1,null);
        ListNode pre = dummyHead;
        while (l1 != null || l2 != null){
            //如果有一个已经遍历结束，为其值赋Integer.MAX_VALUE
            int val1 = l1 == null ? Integer.MAX_VALUE : l1.val;
            int val2 = l2 == null ? Integer.MAX_VALUE : l2.val;

            if(val1 <= val2){
                //新建节点存储此次比较的较小的那个值
                ListNode cur = new ListNode(val1,null);
                //pre指向节点的next指向此次新建节点
                pre.next = cur;
                //res指向最初的头结点（也即两个链表中最小的那个值）
                res = pre == dummyHead ? cur : res;
                //更新pre指向此次新建的节点，好让pre下次指向下次新建的节点
                pre = cur;
                //顺序往后遍历
                l1 = l1.next;
            }else{
                ListNode cur = new ListNode(val2,null);
                pre.next = cur;
                res = pre == dummyHead ? cur : res;
                pre = cur;
                l2 = l2.next;
            }
        }
        return res;
    }

2.

public static ListNode mergeTwoLists1(ListNode l1, ListNode l2) {
        /*递归版本，时间复杂度O(m+n)，空间复杂度O(m+n)
        "从第一次调用merge 时，函数（不同参）就开始入栈，一级一级调用，一级一级入栈，
        直到到达l1,l2满足递归出口才开始返回相应的结果即弹栈到上次调用的地方。如此往复下去，后进调用堆栈的函数先return ，
        一直return 到第一次调用merge时，直接return这个最终1的结果（其实在第一次调用函数时结果就已确定）"
         * */
        //递归出口
        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }
        if(l1.val <= l2.val){
            //此轮排序的最小值节点的next指向应该是下一轮递归调用返回的最小值节点
            l1.next = mergeTwoLists1(l1.next,l2);
            //此轮排序的最小的值即为l1,直接返回l1到被上层递归调用的地方
            return l1;
        }else{
            l2.next = mergeTwoLists1(l1,l2.next);
            //此轮排序的最小的值即为l1,直接返回l2到被上层递归调用的地方
            return l2;
        }

    }