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.

Example:

Input: 1->2->4, 1->3->4

Output: 1->1->2->3->4->4
`

思想

类似归并排序的思想，用两个指针对两个链表进行比较，取较小的一个放在新链表中。最后把较长链表剩下的部分放在新链表中。

代码

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1==NULL){return l2;}
else if(l2==NULL){return l1;}

ListNode* p=l1, *q=l2, *r=NULL;
if (p->val<q->val) {r=p;p=p->next;r->next=NULL;}
else {r=q;q=q->next;r->next=NULL;}
ListNode* head=r;
cout<<r->val<<endl;
    
while (p!=NULL && q!=NULL)
{
    if (p->val<q->val)
    {
        r->next=p;
        r=r->next;  p=p->next;	
    }
    else
    {
        r->next=q; 
        r=r->next; q=q->next;
    }
    cout<<r->val<<endl;
}
    
if(p!=NULL) r->next=p;
if(q!=NULL) r->next=q;

return head;
    

    
}

时间：13ms

注意点：

1. 对于新链表的头结点问题，一种是用假头结点，一种是像我这样判断一下，手动生成头结点。
2. 链表的插入，头插还是尾插

改进

写完之后看别人的代码很精简，把自己的代码也改了一下：

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1==NULL){return l2;}
else if(l2==NULL) return l1;     

ListNode *r=NULL;   //1
if (l1->val<l2->val) {r=l1;l1=l1->next;}    //2
else {r=l2;l2=l2->next;}
    
ListNode* head=r;
    
while (l1 && l2)    //3
{
    if (l1->val<l2->val)
    {
        r->next=l1;
        r=r->next;  l1=l1->next;	
    }
    else
    {
        r->next=l2; 
        r=r->next; l2=l2->next;
    }
}
    
if(l1) r->next=l1;
else r->next=l2;

return head;       
}

1. 将原来的p,q去掉，直接用l1,l2.
2. 取掉r->next=NULL
3. 判断指针直接if(p)，不用if(p!=NULL)