Question

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

运行有错误，但错误很规律，合成表的数据是第一个值固定为一表第一个数，二表第一个数丢失~
#include<stdio.h>
#include<malloc.h>
#define LEN sizeof(struct LNode)
struct LNode
{int data;
struct LNode *next;
}LNode,*LinkList;
int n;
struct LNode *creat(void)//创建链表
{struct LNode *head;
struct LNode *p1,*p2;
n=0;
p1=p2=(struct LNode*)malloc(LEN);
scanf("%d",&p1->data);
head=NULL;
while(p1->data!=0)
{n=n+1;
if(n==1)head=p1;
else p2->next=p1;
p2=p1;
p1=(struct LNode*)malloc(LEN);
scanf("%d",&p1->data);
}
p2->next=NULL;
return(head);
}
void print(struct LNode *head)//打印
{struct LNode *p;
printf("\n链表中的数据有%d个，它们是:\n",n);
p=head;
if(p!=NULL)
do
{printf("%d ",p->data);
p=p->next;
}while(p!=NULL);
}
struct LNode *insert(struct LNode *La,struct LNode *Lb,struct LNode *Lc)//插入
{struct LNode *pa,*pb,*pc;
Lc=pc=La;
pa=La->next;pb=Lb->next;
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;}
n=n+1;};
pc->next=pa?pa:pb;
free(Lb);
return(Lc);
}
main()
{struct LNode *head1,*head2,*head3;
printf("\n请输入第一组有序单链表数据(以0为结束)：\n");
head1=creat();
print(head1);
printf("\n请输入第二组有序单链表数据(以0为结束)：\n");
head2=creat();
print(head2);
head3=insert(head1,head2,head3);
print(head3);
}

Answer 1

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

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

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

代码如下：*/

#include<stdio.h>
#include<stdlib.h>
#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
}