21 合并两个有序链表.md

21、合并两个有序链表

题目：

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

public class ListNode{
    int val;
    ListNode next;
    public ListNode(int x){
        val = x;
    }
}

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

方法一（递归）：

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

分析：

​ 当我第一次看见赋值为函数的时候，感觉一脸懵。。。我想是不是栈和栈帧没学好，不知道函数的运行逻辑了，然而，查了一些栈帧的博客之后，并没卵。

​ 直到我看见了这幅图（来源于 博客）

一下子豁然开朗，原来是从后往前赋值，666。。。造化钟神秀

注意点：

• 理解递归从后往前面赋值的性质；
• 后面两个比较的部分，return返回了当前递归函数的值，这样才能回退到上一层函数。所以说，return的性质不仅仅有退出总函数，还有退回某层递归函数。

复杂度：

​ 时间复杂度：O(min(l1, l2))

​ 空间复杂度：O(l1+l2)

方法二（迭代）：

public ListNode mergeTwoList(ListNode l1, ListNode l2){
    ListNode preHead = new ListNode(-1);
    ListNode pre = preHead;
    
    while(l1 != nul && l2 != null){
        if(l1.val<=l2.val){
            pre.next = l1;
            l1 = l1.next;
        }else{
            pre.next = l2;
            l2 = l2.next;
        }
        pre = pre.next;
    }
    
    pre.next = l1 == null ? l2 :l1;
    return preHead;
}

如果刚接触链表，对第0个节点再赋一个变量，勉强值得一提吧，很简单。