题解 | #合并两个排序的链表#

//思路  比较，尾插法。
 //从头开始比较两个链表的大小，小的结点拿去尾插到一个新链表中，较大的链表指针不动，
 //进入下一次比较。
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
   struct ListNode* p1=pHead1;
   struct ListNode* p2=pHead2;
   if(p1==NULL&&p2!=NULL)//对特殊情况的处理
   {
      return p2;
   }
   else if(p2==NULL&&p1!=NULL)
   {
    return p1;
   }
   struct ListNode* p3head=NULL;//新链表的头和尾
   struct ListNode* p3tail=NULL;
   while(p1&&p2)//进行比较尾插，当其中一个链表为空时停止
   {
      if(p1->val<=p2->val)//p1的val更小时
      {
         if(p3head==NULL)
         {
            p3head=p3tail=p1;
            p1=p1->next;
         }
         else {
            p3tail->next=p1;
            p3tail=p1;
            p1=p1->next;
         }
      }
      else //p2更小时
      {
         if(p3head==NULL)
         {
            p3head=p3tail=p2;
            p2=p2->next;
         }
         else {
            p3tail->next=p2;
            p3tail=p2;
            p2=p2->next;
         }
      }
   }
   if(p1==NULL&&p2!=NULL)//将新链表的尾与未空的链表的头链接
   {
     p3tail->next=p2;
   }
   else if(p2==NULL&&p1!=NULL)
   {
     p3tail->next=p1;
   }
   return p3head;
}