6-2 两个有序链表序列的合并分数 10作者 DS课程组单位 浙江大学本题要求实现一个函数将两个链表表示的递增整数序列合并为一个非递减的整数序列。函数接口定义：List Merge List L1 List L2 ;其中List结构定义如下：typedef struct Node PtrToNode;struct Node ElementType Data; 存储结点数据 Ptr

首先，我们需要创建一个新的链表来存储合并后的结果。我们可以使用三个指针分别指向L1、L2和新链表的当前结点。然后，通过比较L1和L2当前结点的值，将较小的值插入到新链表中，并更新对应的指针。直到其中一个链表遍历完毕，我们将另一个链表剩余的结点直接插入新链表的末尾。最后，返回新链表的头指针即可。

具体实现如下：

List Merge( List L1, List L2 ) { PtrToNode p1 = L1->Next; PtrToNode p2 = L2->Next; PtrToNode p = NULL; PtrToNode head = NULL;

if(p1 == NULL)
    return L2;
if(p2 == NULL)
    return L1;

head = (PtrToNode)malloc(sizeof(struct Node));
head->Next = NULL;
p = head;

while(p1 != NULL && p2 != NULL)
{
    if(p1->Data <= p2->Data)
    {
        p->Next = p1;
        p1 = p1->Next;
    }
    else
    {
        p->Next = p2;
        p2 = p2->Next;
    }
    p = p->Next;
}

if(p1 != NULL)
    p->Next = p1;
if(p2 != NULL)
    p->Next = p2;

L1->Next = NULL;
L2->Next = NULL;
return head;

}