将两个有序链表合并成一个有序链表

//将两个排好序的链表合并成一个有序链表
#include
#include

#define Elem int
#define Status int
#define ERROR 0
#define OK    1
#define bool int
#define true 1
#define false 0

//定义节点类型
typedef struct Node
{
    Elem data;
    struct Node* next;
}Node,*LinkList;

//函数声明
//初始化链表
Status InitLinkList(LinkList* head);
//创建带头节点的链表
LinkList CreateLinkList(LinkList head);
//显示链表数据
void Display(LinkList head);
//由小到大排序
LinkList SortLinkList(LinkList head);
//将两个排好序的链表合并成一个有序链表
LinkList UnionLinkList(LinkList head1,LinkList head2);
//交换两个量
void swap(Elem* e1,Elem* e2);
//计算链表的长度
int GetLength(LinkList head);
//判断链表是否为空
bool IsEmpty(LinkList head);

//主函数
int main()
{
    LinkList head1;
LinkList head2;
printf("Initing and ceating LinkList head1.\n");
    InitLinkList(&head1);
    head1=CreateLinkList(head1);
printf("The length of the LinkList is: %d\n",GetLength(head1));
    Display(head1);
printf("Initing and ceating LinkList head2.\n");
InitLinkList(&head2);
    head2=CreateLinkList(head2);
printf("Sorting the LinkList by increased.\n");
head1=SortLinkList(head1);
head2=SortLinkList(head2);
Display(head1);
Display(head2);
printf("Union head1 and head2.\n");
head1=UnionLinkList(head1,head2);
Display(head1);
    return 0;
}

//初始化链表
Status InitLinkList(LinkList* head)
{
     *head=(Node*)malloc(sizeof(Node));
     if(!head)
       return ERROR;
     (*head)->next = NULL;
     (*head)->data = 0;
     return OK;
}
//创建带头节点的链表
LinkList CreateLinkList(LinkList head)
{
   Node* p = head;
   Node* node = (Node*)malloc(sizeof(Node));
   node->next = NULL;
   node->data =0;
   printf("Enter some numbers:(enter 0 to quit)\n");
   while(scanf("%d",&(node->data)) && node->data !=0)
   {
      if(head->next==NULL)
      {
          head->next = node;
          p = node;
      }
      p->next = node;
      p = node;
      node = (Node*)malloc(sizeof(Node));
      node->next = NULL;
   }
   return head;
}

//显示链表数据
void Display(LinkList head)
{
     Node* p = head->next;
     while(p->next != NULL)
     {
       printf("%d->",p->data);
       p = p->next;
     }
     printf("%d\n",p->data);
}
//由小到大排序 ,用冒泡排序操作
LinkList SortLinkList(LinkList head)
{
Node* first = NULL ;
Node* second = NULL;
int i=0,j=0;
int len = GetLength(head); //获取链表的长度
bool change = true;
for(i = len-1;i >0 && change == true;--i) //外部循环len-1次
{
   //每次从链表的第一个节点开始向后比较
   //每次循环结束了，第len-j一个节点的数据是第j+1大的
   first = head->next; //指向第一个节点
     second = first->next;   //指向第二个节点
   change = false; //每次假设没有交换
   for(j = 0;j < i; ++j,first = first->next, second= second->next)
   {
    if(first->data > second->data)
    {
     swap(&(first->data),&(second->data));
     change = true;
    }
   }
}
return head;
}
//将两个排好序的链表合并成一个有序链表
LinkList UnionLinkList(LinkList head1,LinkList head2)
{
Node* a = head1->next; //指向第一个链表的第一个节点
Node* b = head2->next; //指向第二个链表的第二个节点
Node* c = NULL;
if(!a)
   return head2;
if(!b)
   return head1;
c=head1; //也可以c=head2
while(a != NULL && b != NULL)
{
   if(a->data > b->data)
   {
    c->next = b; //指向b
    c = b;      
    b = b->next; //b向后移动一个
   }
   if(a->data < b->data)
   {
    c->next = a;
    c = a;
    a = a->next;
   }
   if(a->data == b->data) //当有重复的数据时，任选一个就行了
   {
    c->next =a;
    c=a;
    a = a->next;
    b = b->next;
   }
}
c->next = a ? a : b; //最后为不空的那个
    return head1;
}

//交换两个量
void swap(Elem* e1,Elem* e2)
{
Elem temp = *e1;
*e1 = *e2;
*e2 = temp;
}

//计算链表的长度
int GetLength(LinkList head)
{
Node* p = head->next;
int n=0;
if(p == NULL)
   return 0;
for(;p != NULL;p = p->next,++n);
return n;
}

//判断链表是否为空
bool IsEmpty(LinkList head)
{
return (head->next == NULL) ;
}