<> 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
pHead2; if (pHead2 == nullptr) return pHead1; ListNode* head = nullptr; // Header of the new linked list
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 {
ListNode* p = pHead1->val>pHead2->val ? pHead2 : pHead1; // Get the smaller node of the first node of the two linked lists
// Delete the obtained node from the original linked list if (p == pHead1) pHead1 = pHead1->next; else pHead2 = pHead2->
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;
else tail->next = pHead2; return head; // Return to new linked list } };
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)
return pHead2; if (pHead2 == nullptr) return pHead1; ListNode* head = nullptr;
// Header of the new linked list // Insert the end of the smaller node of the first node of the two linked lists into the new linked list if (pHead1->val > pHead2->val){ head = pHead2;
pHead2= pHead2->next; } else{ head = pHead1; pHead1 = pHead1->next; }
// Recursive merge linked list , And insert the tail of the merged linked list after the new linked list head->next = Merge(pHead1, pHead2); return head; // Return to new linked list
} };
Technology