struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        ListNode *head;
        if(pHead1==NULL&&pHead2==NULL) return head;
        if(pHead1==NULL) return pHead2;
        if(pHead2==NULL) return pHead1;
        if(pHead1->val<pHead2->val){
            head=new ListNode(pHead1->val);
            pHead1=pHead1->next;
        }else{
            head=new ListNode(pHead2->val);
            pHead2=pHead2->next;
        }
        ListNode *p=head;
        while(pHead1!=NULL||pHead2!=NULL){
            ListNode *t;
            if(pHead1!=NULL&&pHead2!=NULL){
                if(pHead1->val<pHead2->val){
            		t=new ListNode(pHead1->val);
                    pHead1=pHead1->next;
                }else{
            		t=new ListNode(pHead2->val);
                    pHead2=pHead2->next;
                }
            }else if(pHead1!=NULL&&pHead2==NULL){
                t=new ListNode(pHead1->val);
                pHead1=pHead1->next;
            }else if(pHead1==NULL&&pHead2!=NULL){
                t=new ListNode(pHead2->val);
                 pHead2=pHead2->next;
            }
            p->next=t;
            p=t;
        }
        return head;
    }
};