题目：见leetcode21

解答：

方法一：“假”头指针

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummy(INT_MIN);
        ListNode *tail = &dummy;
        while(l1 && l2)
        {
            if(l1->val < l2->val)
            {
                tail->next = l1;
                l1 = l1->next;
            }else{
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }
        tail->next = l1 ? l1 : l2;
        return dummy.next;
    }

时间复杂度：m+n,空间复杂度：1//一个头结点一个指针

执行时间：8ms，-0.46%

方法二：不要“假”头结点,用一个head指针等效替换，但代码量多了

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
//用head指针等效替换dummy结点
        if(l1 == NULL) return l2;
        if(l2 == NULL) return l1;
        ListNode* head = NULL;
        if(l1->val < l2->val) {head = l1;l1 = l1->next;}
        else {head = l2;l2 = l2->next;}
        ListNode* p = head;
        
        while(l1 && l2)
        {
            if(l1->val < l2->val) {p->next = l1;l1 = l1->next;}
            else {p->next = l2;l2 = l2->next;}
            p = p->next;
        }
        p->next = l1 ? l1 : l2;
        return head;
    }

时间复杂度：m+n,空间复杂度：1//两个指针

执行时间：8ms，-0.46%

方法三：递归

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        //这两句与方法二功能不完全相同
        //这里等效于：“l1 ? l1 : l2 + 初始链表判空” 两个功能的综合
        if(l1 == NULL) return l2;
        if(l2 == NULL) return l1;
        
        if(l1->val < l2->val)
        {
            l1->next = mergeTwoLists(l1->next,l2);
            return l1;
        }else
        {
            l2->next = mergeTwoLists(l2->next,l1);
            return l2;
        }
    }

时间复杂度：m+n,空间复杂度：min{m,n}//递归栈

执行时间：8ms，-0.46%

注意：这里的递归不是尾递归，如果链表长度过长会溢出

尾递归
思考：
1.极限情况：当L1={1,2,3,4,5},而L2={6,7,8,9,10,11},此时的时间复杂度为L1的链表长度，但是实际上这种情况最理想的时间复杂度是1，即直接可以返回合并的有序链表,如何优化？
2.两种递归转非递归：尾递归和单向递归

两次跨越半年的提交🙂.png