用链表合并两个有序列表。
#include <iostream>
using namespace std;
struct ListNode{
int val;
ListNode* next;
ListNode(int x):val(x),next(NULL){
}
};
ListNode * merge(ListNode *list1,ListNode *list2){
ListNode *list3 = NULL;
ListNode *p=NULL;
while(list1!=NULL&&list2!=NULL){
if(list1->val<list2->val){
if(list3==NULL){
list3=list1;
p=list3;
}
else{
p->next=list1;
p=p->next;
}
list1=list1->next;
}
else{
if(list3==NULL){
list3=list2;
p=list3;
}
else{
p->next=list2;
p=p->next;
}
list2=list2->next;
}
}
if(list1!=NULL){
if(list3==NULL)
{
list3=list1;
p=list3;
}
else
p->next=list1;
}
if(list2!=NULL){
if(list3==NULL)
{
list3=list2;
p=list3;
}
else
p->next=list2;
}
return list3;
}
int main() {
ListNode *list1=new ListNode(0);
ListNode *list2=new ListNode(0);
ListNode *p;
p=list1;
int n;
cin>>n;
while(n){
int tmp;
cin>>tmp;
p->next= new ListNode(tmp);
p=p->next;
n--;
}
p=list2;
int m;
cin>>m;
while(m){
int tmp;
cin>>tmp;
p->next= new ListNode(tmp);
p =p->next;
m --;
}
ListNode* list3=merge(list1->next,list2->next);
while(list3!=NULL){
cout<<list3->val<<" ";
list3 = list3->next;
}
return 0;
}