【数据结构】两个有序链表序列的合并（C语言）

函数接口：

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合并为一个非递减的整数序列。要直接使用原序列中的结点，返回归并后的带头结点的链表头指针。

我们先新开个L3作为结果链表，我们分别一个个比较L1和L2中的数据，谁小先取谁放到L3中去，最后如果L1或L2中有一个已经取完了，我们就把剩下的都插入L3中去。

typedef struct Node *PtrToNode;
struct Node{
    ElementType data;
    PtrToNode Next;
};
typedef PtrToNode List;
List Merge( List L1, List L2 )
{
    List L3, Rear;

    L3 = (PtrToNode)malloc(sizeof(struct Node)); 
	L3->Next = NULL;
    Rear = L3; 
    while (L1->Next && L2->Next) { 
		if (L1->Next->Data < L2->Next->Data) { 
           
           Rear->Next = L1->Next;
           L1->Next = L1->Next->Next;
           Rear->Next->Next = NULL;
           Rear = Rear->Next;
		}
		else {
           
           Rear->Next = L2->Next;
           L2->Next = L2->Next->Next;
           Rear->Next->Next = NULL;
           Rear = Rear->Next;
		}
	}
	if ( L1->Next ) { 
        Rear->Next = L1->Next;//看起来好像只复制了一个，单链表可以把后面的一连串都复制给L3
        L1->Next = NULL;
	}
	if ( L2->Next ) { 
        Rear->Next = L2->Next;
        L2->Next = NULL;
	}
	return L3;
}

参考资料：数据结构学习与实验指导（第2版）