浙大数据结构：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;
}