//将两个有序链表并为一个有序链表
#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
    int data;
    struct Node* pNext;
}NODE,*PNODE;

bool GetElem(PNODE pHead,int pos,int * avg);
bool insert_list(PNODE pHead,int pos,int avg);
PNODE create_list();
void traverse_list(PNODE pHead);
void MergeList(PNODE La,PNODE Lb,PNODE Lc);
bool GetElem(PNODE pHead,int pos,int * avg);
int ListLength(PNODE pHead);

int main(void)
{
    int i = 0;
    PNODE La,Lb,Lc;
    La = create_list();
    Lb = create_list();
    Lc = create_list();
    for(i = 0;i<5;i++)    //像链表La中插入1到5
    {
        insert_list(La,i+1,i+1);
    }
    for(i = 0;i<5;i++)   //像链表Lb中插入2到10
    {
        insert_list(Lb,i+1,2*(i+1));
    }
    printf("La = ");
    traverse_list(La);
    printf("\n");
    printf("Lb = ");
    traverse_list(Lb);
    printf("\n");
    MergeList(La,Lb,Lc);
    printf("Lc = ");
    traverse_list(Lc);
    printf("\n");
    return 0;
}

PNODE create_list()                          //创建一个链表
{
    PNODE pHead = (PNODE)malloc(sizeof(NODE));
    if(NULL == pHead)
    {
        printf("动态内存分配失败n");
        exit(-1);
    }
    pHead->pNext = NULL;                   //使得头文件的指针域为空,即该链表为空链表
    return pHead;
}

bool insert_list(PNODE pHead,int pos,int avg)//在链表中插入一个数的函数
{
    int i = 0;
    PNODE p = pHead;                          
    while(p != NULL && i<pos-1)              //得到插入的位置的前一个节点的指针
    {
        i++;
        p = p->pNext;
    }
    if(i>pos-1 || p == NULL)
    {
        return false;                        //pos的值有问题，无法插入，函数返回一个错误的信息
    }
    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    if(NULL == pNew)                         //创建一个节点
    {
        printf("动态内存分配失败");
        exit(-1);
    }
    pNew->data = avg;
    PNODE r = p->pNext;
    p->pNext = pNew;
    pNew->pNext = r;

    return true;
}

bool GetElem(PNODE pHead,int pos,int * avg) //得到链表中某个节点中数据域的值
{
    int i = 1;
    PNODE p = pHead->pNext;
    while(p != NULL && i<pos)
    {
        i++;
        p = p->pNext;
    }
    if(p == NULL || i>pos)
    {
        return false; //pos的值不符合要求，函数返回一个错误的值
    }
    *avg = p->data;
    return true;
}

void traverse_list(PNODE pHead) //遍历整个链表
{
    PNODE p = pHead->pNext;
    while(p != NULL)
    {
        printf("%d\t",p->data);
        p = p->pNext;
    }
    return ;
}

void MergeList(PNODE La,PNODE Lb,PNODE Lc)  //将两个有序链表并为有序链表
{
    int i = 1,j = 1,k = 1,a,b;
    PNODE pA = La->pNext;
    PNODE pB = Lb->pNext;
    int lena = ListLength(La);
    int lenb = ListLength(Lb);
    while(i<=lena && j<=lenb)
    {
        if(pA->data <= pB->data )
        {
            GetElem(La,i,&a);
            insert_list(Lc,k,a);
            i++;
            k++;
        }
        else
        {
            GetElem(Lb,j,&b);
            insert_list(Lc,k,b);
            j++;
            k++;
        }
    }

    while(i<=lena)
    {
        GetElem(La,i,&a);
        insert_list(Lc,k,a);
        i++;
        k++;
    }
    while(j<=lenb)
    {
        GetElem(Lb,j,&b);
        insert_list(Lc,k,b);
        j++;
        k++;
    }

    return ;
}

int ListLength(PNODE pHead)         //计算链表的长度的函数
{
    int i = 0;
    PNODE p = pHead->pNext;
    while(p)
    {
        i++;
        p = p->pNext;
    }

    return i;
}

bool GetElem(PNODE pHead,int pos,int * avg)   //一个从第pos个节点中获得数据的功能的函数
{
    PNODE p = pHead->pNext;
    int i = 1;
    while(p != NULL && i<pos)
    {
        p = p->pNext;
        i++;
    }                                       //使得p指向第pos个节点
    if(i>pos || p == NULL)
    {
        return false;                      //pos的值不符合要求，终止本函数
    }
    *avg = p->data;                         //使得avg所指向的数等于第pos个节点中的数据
    return true;
}