©2020-2024 ioDraw All rights reserved,
Privacy Policy
<>核心考点：链表合并，思维缜密程度
输入两个递增的链表，合并这两个链表并使新链表中的结点仍然是递增排序的。
解析一：（常规）
合并两个链表最常规的做法就是，依次比较两个链表的第一个结点，取较小的结点（此处为递增排序）尾插到一个新链表后，直到其中一个链表当中的结点被取完，最后将未取完结点的链表全部尾插到新链表后即可。
动图演示：
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x),
next(NULL) { } };*/ class Solution { public: ListNode* Merge(ListNode* pHead1,
ListNode* pHead2) { //两个链表中一个为空则返回另一个，两个都为空则返回空 if (pHead1 == nullptr) return
pHead2; if (pHead2 == nullptr) return pHead1; ListNode* head = nullptr; //新链表的头
ListNode* tail = nullptr; //新链表的尾 while (pHead1&&pHead2) //两个链表当中的结点都未取完，则循环继续 {
ListNode* p = pHead1->val>pHead2->val ? pHead2 : pHead1; //获取两个链表第一个结点的较小结点
//从原链表当中删除获取到的结点 if (p == pHead1) pHead1 = pHead1->next; else pHead2 = pHead2->
next; //将获取到的结点尾插到新链表中 if (head == nullptr){ head = p; tail = p; } else{ tail->
next= p; tail = p; } } //将未取完结点的链表全部尾插到新链表后 if (pHead1) tail->next = pHead1;
else tail->next = pHead2; return head; //返回新链表 } };
解析二：（递归）
仔细想想，当我们取出两个链表第一个结点的较小结点后，我们接下来在干什么？
当取出一个较小结点后，我们实际上又是在合并两个新的链表，并将合并后的链表尾插到这个被取出的结点后。
也就是说，我们一直在做一件事，那就是合并两个链表，于是我们可以采用递归的方式解决该问题，最终递归逐层返回时的情况如下：
如此，便完成了两个链表的合并。
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x),
next(NULL) { } };*/ class Solution { public: ListNode* Merge(ListNode* pHead1,
ListNode* pHead2) { //两个链表中一个为空则返回另一个，两个都为空则返回空（递归的结束条件） if (pHead1 == nullptr)
return pHead2; if (pHead2 == nullptr) return pHead1; ListNode* head = nullptr;
//新链表的头 //将两个链表第一个结点的较小结点尾插到新链表后 if (pHead1->val > pHead2->val){ head = pHead2;
pHead2= pHead2->next; } else{ head = pHead1; pHead1 = pHead1->next; }
//递归合并链表，并将合并的链表尾插到新链表后 head->next = Merge(pHead1, pHead2); return head; //返回新链表
} };