浙大数据结构：02-线性结构1 两个有序链表序列的合并
数据结构MOOC
PTA习题
02-线性结构1 两个有序链表序列的合并
用p1,p2存储两个头节点。如果都为空直接返回一个空链表
否则选两条链表中第一个较小的值作为新链表第一个结点。
L1，L2后移一下，然后删除两个没有用的头节点
循环遍历，把值小的插入链表中，直到一个链表遍历完。
再把没遍历完的链表插入新链表中，最后返回头节点
List Merge(List L1,List L2)
{
List p1=L1,p2=L2;
List head=(List)malloc(sizeof(struct Node));
if(p1->Next==NULL&&p2->Next==NULL)
{
head->Next=NULL;return head;
}
head->Next=L1->Next->Data>L2->Next->Data?L2->Next:L1->Next;
List p=head;
L1=L1->Next;L2=L2->Next;
p1->Next=NULL;p2->Next=NULL;
while(L1!=NULL&&L2!=NULL)
{
if(L1->Data<L2->Data)
{
head->Next=L1;
head=head->Next;
L1=L1->Next;
}
else
{
head->Next=L2;
head=head->Next;
L2=L2->Next;
}
}
if(L1)
head->Next=L1;
else if(L2)
head->Next=L2;
return p;
}