题解 | 【清晰图解】#合并两个排序的链表#递归和暴力解法

默认你已经理解题意了哈

题目意思

就是有两个链表，每个链表长度都是n,合并这两个链表成一个新链表，它的结点仍然是递增的，就是这个意思哈 alt

暴力如何解

思路我们可以用暴力来完成。当 l1 和 l2 两个都不是空链表的时候，去判断 l1 和 l2 哪一个链表的头节点的值更加的小，将较小值的节点添加到结果（肯定准备一个数组）里，当一个节点被添加到结果里之后，将对应链表中的节点向后移一位就行；

动图演示，请认真看仔细并理解我上面说的哈

alt

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 使用带头结点的链表解决问题
        // 待输出链表的头部
        ListNode head = new ListNode();

        // 待输出链表的 last 结点
        ListNode last = head;
        while(l1 != null && l2 != null) {
            if(l1.val > l2.val) {
                last.next = l2;
                l2 = l2.next;
            }else{
                last.next = l1;
                l1 = l1.next;
            }
            last = last.next;
        }

        // l1 或 l2 可能还有剩余结点没有合并， 
        // 由于从上面的 while 循环中退出， 那么链表 l1 和 l2 至少有一个已经遍历结束
        if(l1 != null) last.next = l1;
        if(l2 != null) last.next = l2;

        return head.next;

    }
}

这里为了简单方便的处理，给新链表先“安装”一个头结点比如head

1 将 l2 链表的 1 结点摘下来，放到新链表的尾部。
2 将 l2 链表的 2 结点摘下来，然后放到新链表的尾部。
3 将 l1 链表的 3 结点摘下来，然后放到新链表的尾部。同理...
l2 链表被摘完了， l2 == null

最后 l2 链表被“摘”完， l1 链表剩下的部分，“安装”在新链表的尾部。

复杂度分析下

时间复杂度

l1 和 l2 链表都遍历了一遍，那么时间复杂度是 O(n + m) n 和 m 是链表 l1 和 l2 的长度

空间复杂度

只多申请了一个链表头结点，属于常数级别的，那么空间复杂度 O(1)

递归如何解

终止条件：当两个链表都为空时，表示我们对链表已合并完成。 如何递归：我们判断 l1 和 l2 头结点哪个更小，然后较小结点的 next 指针指向其余结点的合并结果。

动图演示，请认真看仔细并理解我上面说的哈

alt

然后考虑递归的终止条件是当 l1==null返回 l2,还是l2==null返回l1, 然后就是判断l1的值是不是小于l2的值呢，如果确实小于递归调l1.next（就是l1的下一个结点），然后还是l2进行合并返回l1就行；反之也是我就不重复了也是一样的形式


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 = mergeTwoList(l1.next, l2);
                   return l1;
                }
          		else {
                   l2.next = mergeTwoLists(l1, l2.next);
                   return l2;
                }
          
        }
}