class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        ListNode* p1=pHead1;
		ListNode* p2=pHead2;
		ListNode *r,*s;
		ListNode* p=(ListNode*)malloc(sizeof(ListNode));
		r=p;
		while(p1!=NULL&&p2!=NULL)
		{
			if(p1->val<p2->val)
			{
				s=(ListNode*)malloc(sizeof(ListNode));
				s->val=p1->val;
				r->next=s;
				r=s;
				p1=p1->next;
			}
			else {
				s=(ListNode*)malloc(sizeof(ListNode));
				s->val=p2->val;
				r->next=s;
				r=s;
				p2=p2->next;
			}
		}
		if(p2!=NULL) p1=p2;
		while(p1!=NULL)
		{
			s=(ListNode*)malloc(sizeof(ListNode));
			s->val=p1->val;
			r->next=s;
			r=s;
			p1=p1->next;
		}
		r->next=NULL;
		return p->next;
    }
};