21.合并两个有序表

Merge Two Sorted Lists

问题描述：

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

知识补充：

测试代码：

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;
    }

性能：

参考答案：

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *q=new ListNode(0);
        ListNode *p=q;
        while(l1&&l2)
        {
           if(l1->val<=l2->val)
           {
               p->next=l1;
               p=p->next;
               l1=l1->next;
           }
            else
            { p->next=l2;
               p=p->next;
               l2=l2->next;}
        }
        if(l1) p->next=l1;
        if(l2) p->next=l2;
       return q->next; 
    }
};

性能：