剑指offer16：输入两个单调递增的链表，合成后的链表满足单调不减规则。

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

1 题目描述

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

2 思路与方法

迭代法：两个链表中较小的头结点作为合并后头结点，之后依次合并两个链表中较小的结点，以此类推，最终合并剩余结点； ListNode* out_list =s->Merge(l1,l4)；

递归法：两个链表中较小的头结点作为合并后头结点，递归；（不推荐递归）

3 C++核心代码

3.1 迭代实现

/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
ListNode* phead = new ListNode();
ListNode* list_new = phead;
while(pHead1 || pHead2){
if(pHead1==NULL){
list_new->next=pHead2;
break;
}
else if(pHead2==NULL){
list_new->next = pHead1;
break;
}
if((pHead1->val)>(pHead2->val))
{
list_new->next = pHead2;
list_new = list_new->next;
pHead2=pHead2->next;
}
else{
list_new->next = pHead1;
list_new = list_new->next;
pHead1=pHead1->next;
}
}
return phead->next;
}
};

3.2 递归实现

/*
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)
return pHead2;
if (!pHead2)
return pHead1; if (pHead1->val < pHead2->val)
pHead1->next = Merge(pHead1->next, pHead2);
else
pHead2->next = Merge(pHead1, pHead2->next); return pHead1->val < pHead2->val ? pHead1 : pHead2;
}
};

4 完整代码

#include <iostream> using namespace std; struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
ListNode* phead = new ListNode();
ListNode* list_new = phead;
while (pHead1 || pHead2){
if (pHead1 == NULL){
list_new->next = pHead2;
break;
}
else if (pHead2 == NULL){
list_new->next = pHead1;
break;
}
if ((pHead1->val)>(pHead2->val))
{
list_new->next = pHead2;
list_new = list_new->next;
pHead2 = pHead2->next;
}
else{
list_new->next = pHead1;
list_new = list_new->next;
pHead1 = pHead1->next;
}
}
return phead->next;
}
};
int main()
{
Solution *s = new Solution();
//vector<int> v = { 2,4,6,1,3,5,7 };
ListNode *l1 = new ListNode();
ListNode *l2 = new ListNode();
ListNode *l3 = new ListNode();
ListNode *l4 = new ListNode();
ListNode *l5 = new ListNode();
ListNode *l6 = new ListNode();
ListNode *l7 = new ListNode();
l1->next = l2;
l2->next = l3;
//l3->next = l4;
l4->next = l5;
l5->next = l6;
l6->next = l7; ListNode* out_list = s->Merge(l1, l4);
while (out_list){
cout << out_list->val << " ";
out_list = out_list->next;
}
cout << endl; system("pause");
return ;
}