思路

使用一个dummyNode作为新的头节点，使用pHead1,pHead2同时遍历两个链表，将值小的那个节点添加到dummyNode为头节点的末尾，并指针后移。

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        ListNode dummyNode(0);
        ListNode *dummyHead = &dummyNode;
        while(pHead1 != NULL && pHead2 != NULL)
        {
            ListNode *current = NULL;
            if(pHead1->val < pHead2->val)
            {    
                current = pHead1;
                pHead1 = pHead1->next;
                dummyHead->next = current;
            }
            else
            {
                current = pHead2;
                pHead2 = pHead2->next;
                dummyHead->next = current;
            }
            dummyHead = current;
        }
        if (pHead1 != NULL)
        {
            dummyHead->next = pHead1;
        }
        if (pHead2 != NULL)
        {
            dummyHead->next = pHead2;
        }
        return dummyNode.next;
    }
};