39-13

假设有两个按元素值递减次序排列的线性表，均以单链表的形式存储，编写算法，将这两个单链表合成一个按值递减的单链表，使用原链表的结点。

没啥好说的，这个有手就行

#include <stdio.h>
#include <stdlib.h>

typedef struct node{
    int data;
    struct node *next;
}LNode,*LinkList;

void TailCreate(LinkList &L)
{
    L=(LinkList)malloc(sizeof(LNode));
    L->next=NULL;
    LNode *p,*r=L;
    int x;
    scanf("%d",&x);
    while(x!=999)
    {
        p=(LNode*)malloc(sizeof(LNode));
        p->data=x;
        p->next=NULL;
        r->next=p;
        r=p;
        scanf("%d",&x);
    }
}

void displayList(LinkList L)
{
    LNode *p=L->next;
    while(p!=NULL)
    {
        printf("%d  ",p->data);
        p=p->next;
    }
}

void Merge(LinkList &A,LinkList &B)
{
    LNode *pa=A->next,*pb=B->next,*r;
    A->next=NULL;
    while(pa&&pb)
    {
        if(pa->data<=pb->data)
        {
            r=pa->next;
            pa->next=A->next;
            A->next=pa;
            pa=r;
        }
        else
        {
            r=pb->next;
            pb->next=A->next;
            A->next=pb;
            pb=r;
        }        
    } 
    if(pb)
        pa=pb;
    while(pa)
    {
        r=pa->next;
        pa->next=A->next;
        A->next=pa;
        pa=r;
    }
    free(B);
}

int main()
{
    LinkList A,B;
    TailCreate(A);
    displayList(A);
    printf("\n");
    TailCreate(B);
    displayList(B);
    printf("\n");
    Merge(A,B);
    displayList(A);
    printf("\n");
    return 0;
}