两路归并的数组与链表的实现方法
本文导语: 代码如下:#include#includeusing namespace std;struct node{ int val; node * next; node(int v) { val=v; next=NULL; }}; node * merge(node* list1 , node * list2){ assert(list1!=NULL&&list2!=NULL); node * res; if(list1->va...
#include
#include
using namespace std;
struct node
{
int val;
node * next;
node(int v)
{
val=v;
next=NULL;
}
};
node * merge(node* list1 , node * list2)
{
assert(list1!=NULL&&list2!=NULL);
node * res;
if(list1->valval)
{
res=list1;
list1=list1->next;
}
else
{
res=list2;
list2=list2->next;
}
node * p = res;
node *p1 =list1,*p2 =list2;
while(p1!=NULL&&p2!=NULL)
{
if(p1->valval)
{
p->next=p1;
p=p->next;
p1=p1->next;
}
else
{
p->next=p2;
p=p->next;
p2=p2->next;
}
}
while(p1!=NULL)
{
p->next=p1;
p=p->next;
p1=p1->next;
}
while(p2!=NULL)
{
p->next=p2;
p=p->next;
p2=p2->next;
}
return res;
}
int * merge(int * arr1,int la, int * arr2,int lb)
{
int i=0,j=0;
int * arr = new int[la+lb];
int t=0;
while(inext=node7;
node7->next=node8;
list2=node5;
}
int main()
{
node * list1;
node * list2;
setLinkData(list1,list2);
int arr1[]={1,6,15,17,19};
int arr2[]={2,4,6,8,10};
int * arr = merge(arr1,5,arr2,5);
node * ans = merge(list1,list2);
//Print result
int length=10;
for(int i=0;i