剑指offer第16题：合并有序链表

如输入->1->2->5->6->8->NULL,和->2->3->7->NULL,要求合并后的链表满足单调不减规则

基本思路

采用循环遍历的方法，分别设置两个指针指向各自的链表头，比较两个指针指向的值，将小者采用尾插法插入新建的链表中；插入新链表结点后的链表往后遍历。直到有一方遍历到NULL，新链表添加另一个链表剩余的部分即可。

算法逻辑

算法过程

代码

ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
    ListNode* head=new ListNode(-1);
    ListNode* tail=head;
    ListNode* p=pHead1;
    ListNode* q=pHead2;
    while(p&&q){
        if(p->val<q->val){
            tail->next=p;
            p=p->next;
            }else{
                tail->next=q;
                q=q->next;
           }
           tail=tail->next;
    }
    if(p){
        tail->next=p;
    }else{
        tail->next=q;
    }
    return head->next;
}