函式介面定義：

List Merge( List L1, List L2 );

其中List結構定義如下：

typedef struct Node *PtrToNode;

struct Node {

ElementType Data; /* 儲存結點資料 */

PtrToNode Next; /* 指向下一個結點的指標 */

};

typedef PtrToNode List; /* 定義單鏈表型別 */

L1和L2是給定的帶頭結點的單鏈表，其結點儲存的資料是遞增有序的；函式Merge要將L1和L2合併為一個非遞減的整數序列。應直接使用原序列中的結點，返回歸併後的帶頭結點的連結串列頭指標。

裁判測試程式樣例：

#include <stdio.h>

#include <stdlib.h>

typedef int ElementType;

typedef struct Node *PtrToNode;

struct Node {

ElementType Data;

PtrToNode Next;

};

typedef PtrToNode List;

List Read(); /* 細節在此不表 */

void Print( List L ); /* 細節在此不表；空連結串列將輸出NULL */

List Merge( List L1, List L2 );

int main()

{

List L1, L2, L;

L1 = Read();

L2 = Read();

L = Merge(L1, L2);

Print(L);

Print(L1);

Print(L2);

return 0;

}

/* 你的程式碼將被嵌在這裡 */

輸入樣例：

3

1 3 5

5

2 4 6 8 10

輸出樣例：

1 2 3 4 5 6 8 10

NULL

NULL

由後面打印出的兩個NULL可以看出，這個操作是將L1,L2的節點重新掛在L3的節點上,L1,L2,L3均為頭節點，最後實現程式碼

List Merge( List L1, List L2 )

{

List pa,pb,pc,L;

L = (List)malloc(sizeof(struct Node));

pa=L1->Next; // 指向pa第一個元素

pb=L2->Next; // 指向pb第一個元素

pc = L;

while(pa && pb)

{

if(pa->Data <= pb->Data)

{

pc->Next = pa;

pc = pa;

pa = pa->Next;

}

else

{

pc->Next = pb;

pc = pb;

pb = pb->Next;

}

}

if(pa)

{

pc->Next = pa;

}

if(pb)

{

pc->Next = pb;

}

L1->Next = NULL;

L2->Next = NULL;

return L;

}