21. 合并两个有序链表

一、思路：

采用双指针法，每次比较两个指针指向的结点的大小，将小的放入第三个链表并将指针向后移动一个结点，直到有一个指针为空。最后将非空的指针后面的结点放入第三个链表。

二、代码（C++）：

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *l3=new ListNode(0);    //新建一个带头结点链表
        ListNode *tail=l3;    //用tail指针指向新链表的尾部
        ListNode *p=l1, *q=l2;    //用两个指针分别指向两个链表
        while(p&&q)    //依次比较，将较小的结点放入新链表
        {
            if(p->val<=q->val)
            {
                tail->next=p;
                tail=p;
                p=p->next;
            }
            else
            {
                tail->next=q;
                tail=q;
                q=q->next;
            }
                
        }
        if(p)    //将非空指针后面的结点放入新链表
        {
            tail->next=p;
        }
        if(q)
        {
            tail->next=q;
        }
        return l3->next;
    }