合并两条有序链表
- - CSDN博客编程语言推荐文章有序链表的合并是面试的时候常考的一道链表算法题:. 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则(即升序). 对于这道题目有两种解法:一是非递归形式,二是递归形式. 1.非递归算法,我们解题思路如下:. (1)先考虑这几种特殊情况,. 如果两条链表相等,我们将返回任意一条即可;.
有序链表的合并是面试的时候常考的一道链表算法题:
输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则(即升序)。
对于这道题目有两种解法:一是非递归形式,二是递归形式。
1.非递归算法,我们解题思路如下:
(1)先考虑这几种特殊情况,
如果两条链表相等,我们将返回任意一条即可;
如果一条链表为空,另一条不为空,那么我们返回不为空的那条链表即可;
(2)这些情况处理完之后,我们再来进行下一步骤,
先确定两条不为空的链表排序后的头部,也就是比较第一个节点值的大小;
排序新链表头部确定好后,我们再来比较后面的值进行连接,这里维护一个尾指针比较好操作;
最后这个问题容易被忽略,比如说,链表1为 1->3->5;链表2为 2->4->6
在前面的步骤中已经将链表1处理完,但链表2里面还有6未处理,所以对于这种情况,我们就应该检测,如果一条链表已经为空(即处理完),另一条链表不为空时,我们就直接将不为空的链表链在排序新链表的尾部。
代码如下:
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
if(pHead1==pHead2)
return pHead1;
if(pHead1==NULL)
return pHead2;
if(pHead2==NULL)
return pHead1;
ListNode* NewHead=NULL;
ListNode* tail=NULL;
ListNode* cur1=pHead1;
ListNode* cur2=pHead2;
if(cur1->val < cur2->val)
{
NewHead=cur1;
tail=cur1;
cur1=cur1->next;
}
else
{
NewHead=cur2;
tail=cur2;
cur2=cur2->next;
}
while(cur1 && cur2)
{
if(cur1->val < cur2->val)
{
tail->next=cur1;
tail=tail->next;
cur1=cur1->next;
}
else
{
tail->next=cur2;
tail=tail->next;
cur2=cur2->next;
}
}
if(cur1==NULL)
{
tail->next=cur2;
tail=tail->next;
}
else
{
tail->next=cur1;
tail=tail->next;
}
return NewHead;
}
2.递归方式
递归的问题就是考虑两件事情:一是递归结束条件,二是子问题的解决。
这里直接给出代码:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
if(pHead1==pHead2)
return pHead1;
if(pHead1==NULL)
return pHead2;
if(pHead2==NULL)
return pHead1;
if(pHead1->val < pHead2->val)
{
pHead1->next=Merge(pHead1->next,pHead2);
return pHead1;
}
else // pHead1->val >= pHead2->val
{
pHead2->next=Merge(pHead1,pHead2->next);
return pHead2;
}