剑指Offer 合并两个排序的链表

题目描述

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

思路：

用2个新节点，一个用来存放新链表的头节点，另一个用来移动。当p1，p2有一个到尾部的时候，结束循环，讲另一条链剩下的插到新链尾部。

注意：需要考虑链表p1，p2为空的情况。

AC代码：

 /*
 struct ListNode {
     int val;
     struct ListNode *next;
     ListNode(int x) :
             val(x), next(NULL) {
     }
 };*/
 class Solution {
 public:
     ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
     {
         if(!pHead1&&!pHead2)
             return NULL;
         if(!pHead1)
             return pHead2;
         if(!pHead2)
             return pHead1;

         ListNode *root=new ListNode();
         ListNode *r=root;

         while(pHead1&&pHead2)
         {

             if(pHead1->val<pHead2->val)
             {
                 r->next=pHead1;
                 pHead1=pHead1->next;
             }
             else
             {
                 r->next=pHead2;
                 pHead2=pHead2->next;
             }

             r=r->next;
         }

         if(pHead1)
             r->next=pHead1;
         if(pHead2)
             r->next=pHead2;        

         return root->next;

     }
 };