<> Core test site ： Linked list merge , Degree of meticulous thinking

Enter two incremental linked lists , Merge the two linked lists and make the nodes in the new linked list still sort incrementally .

Analysis I ：（ routine ）

The most common way to merge two linked lists is , Compare the first node of the two linked lists in turn , Take the smaller node （ Incremental sort here ） After inserting the tail into a new linked list , Until one of the nodes in the linked list is taken , Finally, insert all the tails of the linked list without the end point into the new linked list .

Dynamic diagram demonstration ：

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x),
next(NULL) { } };*/ class Solution { public: ListNode* Merge(ListNode* pHead1,
ListNode* pHead2) { // If one of the two linked lists is empty, the other is returned , If both are empty, null is returned if (pHead1 == nullptr) return
ListNode* tail = nullptr; // Tail of new linked list while (pHead1&&pHead2) // The nodes in the two linked lists are not finished , Then the cycle continues {
next; // Insert the obtained node tail into the new linked list if (head == nullptr){ head = p; tail = p; } else{ tail->
next= p; tail = p; } } // Insert all the tails of the linked list without the end point into the new linked list if (pHead1) tail->next = pHead1;
Analysis II ：（ recursion ）
Think about it , When we take out the smaller node of the first node of the two linked lists , What are we doing next ?

After taking out a small summary point , We are actually merging two new linked lists , And insert the tail of the merged list into the extracted node .

in other words , We've been doing one thing , That is to merge two linked lists , So we can solve the problem recursively , The final recursion returns layer by layer as follows ：

such , This completes the merging of the two linked lists .
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x),
next(NULL) { } };*/ class Solution { public: ListNode* Merge(ListNode* pHead1,
ListNode* pHead2) { // If one of the two linked lists is empty, the other is returned , If both are empty, null is returned （ End condition of recursion ） if (pHead1 == nullptr)