链表——合并两个“非递减”链表

①自己写的错是：写成了两个链表第一个比较，然后放在一号位和二号位。
实际上，不一定一定是121212，可能是{1,2,3,4,5}和{2,2,2,2,2,2}，也就是说，每次
只选出两指针中一个最小的值，采用了哪一个就移动下一位，没被采用的那个指针不动。

不递归

/*
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)return pHead2;
        if(!pHead2)return pHead1;

        ListNode* result;
        if( pHead1->val>=pHead2->val )
        {
            result = pHead2;
            pHead2 = pHead2->next;
        }else{
            result = pHead1;
            pHead1 = pHead1->next;
        }    //result头节点一定分配完毕了
        ListNode* p = result;
        while(pHead1&&pHead2)
        {
               if(pHead1->val<=pHead2->val)
               {
                   p->next = pHead1;
                   pHead1 = pHead1->next;
                   p =p->next;
               }else{
                    p->next = pHead2;
                    pHead2 = pHead2->next;
                    p = p->next;
               }
        }
        if(pHead1==NULL)
        {
            p->next = pHead2;
        }
        if(pHead2==NULL){
            p->next = pHead1;
        }
        return result;



    }
};

递归版本

 ListNode* result;
        if(!pHead1)return pHead2;
        if(!pHead2)return pHead1;
        if(pHead1->val<=pHead2->val)
        {
            pHead1->next = Merge(pHead1->next,pHead2);
            return pHead1;
        }else{
            pHead2->next = Merge(pHead2->next,pHead1);
            return pHead2;
        }