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

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        ListNode* p1 = new ListNode(-1);	// 创建一个头节点，指向pHead1
		p1->next = pHead1;
		ListNode* result = p1;	// 创建一个新节点保存p1，最终返回这个节点的next节点即可
		while(p1->next && pHead2){	// 当两个链表都不为空时，进入循环
			if(p1->next->val > pHead2->val){	// 当头节点的下一个节点大于等于2的节点时
				ListNode* temp1 = p1->next;		// 用temp1保存头节点的下一个节点
				ListNode* temp2 = pHead2->next;	// 用temp2保存2的下一个节点
				p1->next = pHead2;				// 将头结点的下一个节点替换为小的2的节点
				p1->next->next = temp1;			// 将头节点的下一个节点的下一个节点指向大的temp1
				pHead2 = temp2;					// 更新pHead2的节点
				p1 = p1->next;					// 更新p1节点
			}
			else p1 = p1->next;					// 如果头节点的下一个节点等于2的节点更新p1节点即可
		}
		if(pHead2) p1->next = pHead2;			// 循环结束，如果pHead2不为空，则pHead2全是大的，让p1直接指向pHead2
		return result->next;					// 是在pHead1中改的，直接返回pHead1
    }
};