将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

https://leetcode-cn.com/problems/merge-two-sorted-lists/

示例1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例2：

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

示例3：

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

提示：

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

Java解法

思路：

• 合并有序链表是基本操作，其他问题中的步骤会用到这一步，中间只涉及到链接的切断、连接
• 考虑结点比较+递归方法完成操作

package sj.shimmer.algorithm;

/**
 * Created by SJ on 2021/2/7.
 */

class D14 {
    public static void main(String[] args) {
        System.out.println(mergeTwoLists(ListNode.createNode(new int[]{1,2,4}),ListNode.createNode(new int[]{1,3,4})));
        System.out.println(mergeTwoLists(ListNode.createNode(new int[]{}),ListNode.createNode(new int[]{})));
        System.out.println(mergeTwoLists(ListNode.createNode(new int[]{}),ListNode.createNode(new int[]{0})));

    }
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null&&l2 == null) {
            return null;
        }
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }

        ListNode head = null;

        if (l1.val>l2.val) {
            head = l2;
            head.next = mergeTwoLists(l1,l2.next);
        }else {
            head = l1;
            head.next = mergeTwoLists(l1.next,l2);
        }
        return head;
    }
}

官方解

https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/

1. 递归

   思路一样，不过好像 又是优雅。。。

   class Solution {
       public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
           if (l1 == null) {
               return l2;
           } else if (l2 == null) {
               return l1;
           } else if (l1.val < l2.val) {
               l1.next = mergeTwoLists(l1.next, l2);
               return l1;
           } else {
               l2.next = mergeTwoLists(l1, l2.next);
               return l2;
           }
   
       }
   }
   

   • 时间复杂度：O(n+m)
   • 空间复杂度：O(n+m)

2. 迭代

   • 声明一个假的头结点用于记录要返回的头结点，再声明一个指针结点，记录每次比较的结果及下一次比较的位置
   • 比较结点，结果作为指针结点的next，指针后移，直到完成比较

   class Solution {
       public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
           ListNode prehead = new ListNode(-1);
   
           ListNode prev = prehead;
           while (l1 != null && l2 != null) {
               if (l1.val <= l2.val) {
                   prev.next = l1;
                   l1 = l1.next;
               } else {
                   prev.next = l2;
                   l2 = l2.next;
               }
               prev = prev.next;
           }
   
           // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
           prev.next = l1 == null ? l2 : l1;
   
           return prehead.next;
       }
   }
   

   优势，占用空间少，同时时间上也不会拉长

   • 时间复杂度：O(n+m)
   • 空间复杂度：O(1)，只需要几个结点的位置来记录，不像递归涉及到多个方法的嵌套，存储空间拉长