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

//这题由于限制了空间复杂度为O1，因此最简单粗暴的办法，把两个链表遍历一边，所有值拿出来，存进数组，排序，建一个新链表，这种思路是不行的。我们只能在原地构建一个新链表——其实就是把几个指针大家挪来挪去，你指我指你。
//思路上借鉴了之前的反转链表的题解，想象成我们建了一个新的链表，然后把旧链表上的节点一个个“拆”下来，放到新链表上去。
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        ListNode* p1=pHead1;
		ListNode* p2=pHead2;
		ListNode* newList=new ListNode(0);//构造一个出来。不然空指针指向的空对象，也是没有成员对象next的。另外newList的存在主要是为了记录新链表的入口。
		ListNode* current=newList;
		while (p1 && p2) {
			if(p1->val > p2->val)
			{
				current->next=p2;//将current指向更小的那个节点，并移动current
				current=current->next;
				p2=p2->next;//移动p1
			}else {
				current->next=p1;
				current=current->next;
				p1=p1->next;
			}
		}
		current->next=p1? p1:p2;//剩下的直接整段接上去就行了。
		return newList->next;
    }
};