Linked list - merge two sorted lists

subject ：

Enter two incremental linked lists , The length of a single linked list is n, Merge these two linked lists and make the nodes in the new linked list still be sorted incrementally .
requirement ： Spatial complexity O(1)O(1), Time complexity O(n)O(n)
Such as the input {1,3,5},{2,4,6} when , The combined linked list is {1,2,3,4,5,6}, So the corresponding output is {1,2,3,4,5,6}, The conversion process is shown in the figure below ：

Their thinking ：

A very important message in the title is ： Both linked lists are incremental .
Explain the first node of the final synthesized list , It must be the smaller of the head nodes of the two linked lists . And the next node of the result linked list , It should be the smaller of the next nodes of the two linked lists .
Based on this information, we can write code .

function ：

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        ListNode* list=new ListNode(0);// Initialize a val by 0,next by null The node of , As the head node of the result linked list .
        ListNode* cur=list;//cur It needs to change with the process .list Can't , Eventually return list->next, The final linked list .
        while(pHead1 && pHead2){
            if(pHead1->val<pHead2->val){
                cur->next=pHead1;
                pHead1=pHead1->next;
            }else{
                cur->next=pHead2;
                pHead2=pHead2->next;
            }
            cur=cur->next;
        }
        // Connect the remaining parts of the two linked lists to the result linked list 
        cur->next=pHead1?pHead1:pHead2;
        return list->next;
    }
};