数据结构：将两个有序的单链表合并成一个有序的单链表，要求用原表的结点空间。

Question

将两个有序的单链表合并成一个有序的单链表，要求用原表的结点空间。4月20日晚八点前！先行谢过！

Answer 1

#include "stdlib.h"
#include "time.h"
struct link
{
int data;
struct link *next;
};
//不带头节点的链表
struct link *CreateLink(int n)
{
struct link *head=NULL,*p=NULL,*q=NULL;
srand( n*1000);
int temp = rand()%10;
head = (struct link *)malloc(sizeof(struct link));
head->data = temp;
head->next = NULL;
p = head;
for (int i=1; i<n; i++)
{
q = (struct link *)malloc(sizeof(struct link));
temp = temp+rand()%100;
q->data = temp;//ascend
q->next = NULL;
p->next = q;
p = q;
}
return head;
}
void PrintLink(struct link *head)
{
struct link *p=head;
printf("\nData in the Link:");
while (p!=NULL)
{
printf("%d ",p->data);
p = p->next;
}
}
struct link *MergeLink(struct link *h1, struct link *h2)
{
struct link *head;
struct link *head1=h1,*head2=h2;

//哪个链表第一个节点值小，则把它的头指针作为合并后的头指针
if (h1->data>h2->data)
{
head1 = h2;
head2 = h1;
}
head = head1;
struct link *tmp=NULL;
while (head2 != NULL)
{
while ( (head1->next->data < head2->data) && head1->next!=NULL)
{
head1 = head1->next;
}
tmp = head2;
head2 = head2->next;
tmp->next = head1->next;
head1->next = tmp;
}
return head;
}
int main()
{
struct link *head1=NULL,*head2=NULL;
head1 = CreateLink(10);
PrintLink(head1);
head2 = CreateLink(13);
PrintLink(head2);
struct link *head=NULL;
head = MergeLink(head1,head2);
PrintLink(head);
return 1;
}

Answer 2

#include <stdio.h>
#include <stdlib.h>
#define null 0
typedef struct LNode
{
int data ;
struct LNode *next ;
}LNode , *LinkList;void CreateList_L(LinkList L,int n)
{
int i;
LinkList p;
for(i=n;i>0;--i)
{
p=(LinkList)malloc(sizeof(LNode));
printf(" input numbers: \n");
scanf("%d",&p->data);
p->next=L->next;
L->next=p;
}
}
main()
{
int n1,n2;
LinkList La,Lb,Lc,pa,pb,pc;
printf("input the n1:");
scanf("%d",&n1);
printf("input the n2:");
scanf("%d",&n2);
La=(LinkList)malloc(sizeof(LNode));
La->next=null;
CreateList_L(La,n1);
Lb=(LinkList)malloc(sizeof(LNode));
Lb->next=null;
CreateList_L(Lb,n2);
Lc=(LinkList)malloc(sizeof(LNode));
Lc->next=null;
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;
pc=La->next;
while(pc)
{
printf("%d",pc->data);
pc=pc->next;
}
}

Answer 3

不管你是用什么算法给链表排序的，，都可以用插入排序的方式将第二个链表插入到第一个链表啊，