题解 | #合并两个排序的链表#

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
		//添加一个表头
        ListNode* pHead3 = new ListNode(0);
		pHead3->next = pHead1;
		ListNode* res = pHead3;//记录表头
		while(pHead1 && pHead2)
		{
			if(pHead1->val <= pHead2 ->val)
			{
				pHead3 ->next = pHead1;
				pHead3 = pHead3->next;
				pHead1 = pHead1->next;
			}
			else
			{
				pHead3 ->next = pHead2;
				pHead3 = pHead3->next;
				pHead2 = pHead2->next;
			}
		}
		//如果执行完后，pHead1不为空，则把该链表余下的元素接在后面，否则接pHead2
		pHead3->next = (pHead1)?pHead1:pHead2;
		return res->next;
    }
};

解题思路：当链表1和2都不为空时，执行操作：如果链表1的数据小于链表2的数据，则把表1的结点链接到储存的表pHead3中，否则链接表2的结点。执行完后，把余下的不为空的链表全部链接到后面。