<>核心考点:链表合并,思维缜密程度

输入两个递增的链表,合并这两个链表并使新链表中的结点仍然是递增排序的。

解析一:(常规)

合并两个链表最常规的做法就是,依次比较两个链表的第一个结点,取较小的结点(此处为递增排序)尾插到一个新链表后,直到其中一个链表当中的结点被取完,最后将未取完结点的链表全部尾插到新链表后即可。

动图演示:

/* 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; //返回新链表
} };

技术
下载桌面版
GitHub
Gitee
SourceForge
百度网盘(提取码:draw)
云服务器优惠
华为云优惠券
腾讯云优惠券
阿里云优惠券
Vultr优惠券
站点信息
问题反馈
邮箱:[email protected]
吐槽一下
QQ群:766591547
关注微信