将两个有序单链表合并成一个有序的单链表，要求用原表的节点空间

下面是我写的，希望可以供你做个参考。

/*递增链表的合并思路：先建表La，Lb。对两个链表进行排序，然后合并。

也许最大的问题根本不是合并的本身，而是合并前的排序。本以为排序比较简单，做了之后才发现，有许多细节部分需要注意。这里用的是插入排序法。

代码如下：*/

#include
#include
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -2
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef int ElemType;
typedef int Status;
typedef struct Lnode *Linklist;//这里稍微做了下改进，效果是一样的
typedef struct Lnode{
ElemType data;
Linklist next;
}LNode;
void DisplayList_L();
void CreatList_L();
void MergeList_L();
void INSERTION_SORT();
//*****************主函数部分******************
int main() {
int n, m;
Linklist La = NULL, Lb = NULL, Lc = NULL;//初始化头节点是La，Lb，Lc的单链表

printf("请输入链表La的结点数： \n");
scanf("%d", &n);
CreatList_L(&La, n);//创建头节点La的单链表
DisplayList_L(La);
INSERTION_SORT(&La);
DisplayList_L(La);
printf("请输入链表Lb的结点数：\n");
scanf("%d",&m);
CreatList_L(&Lb, m);//创建头节点Lb的单链表
DisplayList_L(Lb);

INSERTION_SORT(&Lb);
DisplayList_L(Lb);

MergeList_L(&La, &Lb, &Lc);
DisplayList_L(Lc);

system("PAUSE");
}
//****************展示单链表*********************
void DisplayList_L(Linklist L) {
Linklist p = L->next;
while(p
) {
printf("%5d\n",p->data);
p = p->next;
}
printf("\n\n");
}
//*****************创建单链表*******************
void CreatList_L(Linklist *L, int n) {
int a, i;
Linklist p;
(*L)=(Linklist)malloc (sizeof(LNode));
(*L)->next = NULL;
for(i=n; i>0; --i){
p=(Linklist)malloc(sizeof(LNode));
printf("请输入第%d个节点值：", i);
scanf("%d", &a);
p->data= a;
p->next = (*L)->next;
(*L)->next = p;
}
}
//*****************合并函数********************
void MergeList_L(Linklist *La, Linklist *Lb, Linklist *Lc){
Linklist pa, pb, pc;
pa = (*La)->next;
pb = (*Lb)->next;
(*Lc) = pc = (*La);
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;
}
}
pc->next = pa? pa:pb;
free(Lb);
}
//**************对链表进行选择排序**************
void INSERTION_SORT(Linklist *ptr) {
Linklist temp, p, q, L;//temp 是当前关键字元素
CreatList_L(&L, 0);//初始化已排序的链表 l

temp = (*ptr)->next;//排序之前，先将*ptr的头节点放入L单链表中，以便后续操作
(*ptr)->next = temp->next;
temp->next = NULL;
L->next = temp;

while((*ptr)->next) {
temp = (*ptr)->next;
(*ptr)->next = temp->next;
p = L->next;//初始化p， q
q = L;
while( (q->next != NULL)&&(temp->data) > p->data ){//查找关键字元素temp在已排序链表的合适位置
q = p;
p = p->next;
}
temp->next = p;
q->next = temp;
}
*ptr = L;//将已排序链表l赋值于原头节点*ptr
}