核心考点:链表合并,思维缜密程度
输入两个递增的链表,合并这两个链表并使新链表中的结点仍然是递增排序的。
解析一:(常规)
合并两个链表最常规的做法就是,依次比较两个链表的第一个结点,取较小的结点(此处为递增排序)尾插到一个新链表后,直到其中一个链表当中的结点被取完,最后将未取完结点的链表全部尾插到新链表后即可。
动图演示:
/*
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; //返回新链表
}
};