链表归并的实现

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <malloc.h>
typedef struct node
{
  int num;
  struct node* next;
}Node,*pNode;
typedef enum {false,true}bool;
pNode sort(pNode head)
{
    pNode p3=head;
    pNode p2,p1,p4,p5;
    while(p3->next->next!=NULL)//注意链表向前推进的方式

        {
            p2=p3->next;
            p5=p2;
            p1=p2;
            bool flag=false;
            while(p1->next!=NULL)//内存循环终止的条件

                {
                    if(p5->num>p1->next->num)//找出原链表中剩余节点中值最小的那个节点

                        {
                            p5=p1->next;
                            p4=p1;
                            flag=true;
                        }
                    p1=p1->next;
                }
            if(flag)//交换两个节点的顺序，值小的节点往前调

                {
                    if(p2==p4)//此种情况为要交换顺序的两个节点相邻

                        {
                            p2->next=p5->next;
                            p5->next=p2;
                            p3->next=p5;
                        }
                    else//这种情况为要交换的两个节点不相邻

                        {
                            pNode temp=p5->next;
                            p5->next=p2->next;
                            p3->next=p5;
                            p4->next=p2;
                            p2->next=temp;
                        }
                }
            p3=p3->next;
        }
/*cout<<endl<<"After sort the result is: "<<endl;
pNode temp=head;
temp=temp->next;
while(temp!=NULL)
{
cout<<temp->num<<' ';
temp=temp->next;
}
cout<<endl<<endl;
*/
    return head;
}
int createlist(pNode *head)
{
    if((*head=(pNode)malloc(sizeof(Node)))==NULL)
        {
            printf("malloc head node failure\n");
            return -1;
        }
    (*head)->next=NULL;
    pNode tmp,cur;
    int i=0;
    int a;
    scanf("%d",&a);
    while (a!=999)
    {
        cur=*head;
        i++;
        if((tmp=(pNode)malloc(sizeof(Node)))==NULL)
            {
                printf("malloc 第［%d］个内存失败",i);
                return -1;
            }
        tmp->num=a;
        while((cur->next!=NULL)&&cur->next->num<a)
            cur=cur->next;
        tmp->next=cur->next;
        cur->next=tmp;
        scanf("%d,&a");
        /*tmp->next=NULL;
        if(i==1)
            {
                (*head)->next=tmp;
                cur=tmp;
                scanf("%d,&a");
            }
        cur->next=tmp;
        cur=tmp;*/
    }
    //(*head)=sort(*head);

    return 0;
}
pNode MergeTwoList(pNode head1,pNode head2)
{
    pNode pcur1=head1->next;
    pNode pcur2=head2->next;
    pNode head=(pNode)malloc(sizeof(Node));
    pNode tmp_head=head;
    if(head==NULL)
        {
            printf("malloc new head failure\n");
            return NULL;
        }
    while(pcur1!=NULL&&pcur2!=NULL)
        {
            if(pcur1->num<pcur2->num)
                {
                    tmp_head->next=pcur1;
                    pcur1=pcur1->next;
                }
            else
                {
                    tmp_head->next=pcur2;
                    pcur2=pcur2->next;
                }
            tmp_head=tmp_head->next;
        }
    if(pcur1==NULL)
        {
            tmp_head->next=pcur2;    
        }
    else
        {
            tmp_head->next=pcur1;
        }
    return head;
}
int main()
{
    pNode head1,head2;
    if(createlist(&head1)==-1)
        printf("create list1 failure\n");
    /*while(head1->next!=NULL)
    {
        head1=head1->next;
        printf("%d\n",head1->num);
    }*/
    if(createlist(&head2)==-1)
        printf("create list2 failure\n");
    /*while(head2->next!=NULL)
    {
        head2=head2->next;
        printf("%d\n",head2->num);
    }*/
    pNode newhead=MergeTwoList(head1,head2);
    while(newhead->next!=NULL)
    {
        newhead=newhead->next;
        printf("%d\n",newhead->num);
    }
    return 0;
}