题解 | #合并有序链表#

题解一创建辅助头节点
图示：

复杂度分析：
时间复杂度：O(M+N))，最差为轮流插入两个链表，最终需要遍历完两个链表，所以为O(M+N))
空间复杂度：O（1），只使用了有限常数个变量；

实现如下：

class Solution {
public:
    /**
     *
     * @param l1 ListNode类
     * @param l2 ListNode类
     * @return ListNode类
     */
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // write code here
        ListNode* t = new ListNode(0);  //辅助头节点
        ListNode* p =t;
        while(l1 && l2){
            if(l1->val > l2->val) {p->next = l2; l2 = l2->next;}  
            else {p->next = l1; l1 = l1->next;}
            p = p->next;
        }
        //l1为空 直接在后面拼接l2
        if(!l1) p->next = l2;
        else p->next = l1;
        return t->next;
    }
};

题解二： 不做辅助节点
先比较l1,l2头节点，确定用哪个作为新头，剩下的与题解一相同
复杂度分析：
时间复杂度：O(M+N)，最差为轮流插入两个链表，最终需要遍历完两个链表，所以为O(M+N))
空间复杂度：O(1)，只使用了有限常数个变量；
实现如下：

class Solution {
public:
    /**
     *
     * @param l1 ListNode类
     * @param l2 ListNode类
     * @return ListNode类
     */
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        //有一个为空返回另一个
        if(!l1) return l2;
        if(!l2) return l1;
        ListNode * p,*q,*head;
        if(l1->val > l2->val) {head = l2;l2 = l1;}  // 确定新头
        else head = l1;
        p = head->next;
        q = head;
        while(p && l2){
            if(p->val > l2 ->val){q->next = l2;l2 = l2->next;}
            else {q ->next = p;p = p->next;}
            q = q->next;
        }
        //有一个为空，那么直接在后面拼接
        if(p) q->next = p;
        else q->next = l2;
        return head;
    }
};