博客

将链表La和Lb合并为Lc，


条件:

不给Lc分配新内存(即调整Lc的指针指向两链表符合条件的节点);

主要算法

List *T_O(LNode La,LNode Lb,LNode Lc){
/*判断两链表是否存在一处拜访完，一处有几个村没拜访的情况，如果有就判断是哪几个村，并挨家挨户拜访*/
    if(La==NULL||Lb==NULL){
        if(La==NULL&&Lb!=NULL){
            Lc=Lb;
            Lc->next=T_O(La,Lb->next,Lc->next);
        }else if(Lb==NULL&&La!=NULL){
            Lc=La;
            Lc->next=T_O(La->next,Lb,Lc->next);
        }else{ return Lc;}
        return Lc;
    }
    /*
    if(La==NULL){
        Lc=Lb;
        return;
    }else if(Lb==NULL){
        Lc=La;
        return;
    }
    */
    LNode pa=La;
    LNode pb=Lb;//这里也可以不用重新任命对象完成任务，可直接御驾亲征
    if(pa->data<=pb->data){
        Lc=(LNode)malloc(sizeof(List));
        Lc=pa;//使Lc指向搜刮的那一个村
        Lc->next=T_O(La->next,Lb,Lc->next);//抢完一个换下一个
    }else{
        Lc=(LNode)malloc(sizeof(List));
        Lc=pb;
        Lc->next=T_O(La,Lb->next,Lc->next);
    }
    return Lc;
}

主要代码

#include <stdio.h>
#include <stdlib.h>
typedef struct node{
    struct node *next;
    int data;
}*LNode,List;

List *InitList(LNode L,int a[],int n){
    L=(LNode)malloc(sizeof(List));
    //printf("a值为%d\n",a[n]);
    
    //printf("n为%d\n",n);
    if(n<=3){
    L->data=a[n];
    //printf("L值为%d\n",L->data);
    n=n+1;
    //printf("%d",a[n]);
    L->next=InitList(L->next,a,n);
    }else {
        L=NULL;
        return L;}
    
    return L;
}

void dispList(LNode L){
    if(L!=NULL){
        printf("%d ",L->data);
        dispList(L->next);
    }else return;
    printf("\n");
}

List *T_O(LNode La,LNode Lb,LNode Lc){
    if(La==NULL||Lb==NULL){
        if(La==NULL&&Lb!=NULL){
            Lc=Lb;
            //printf("此时Lc的值为%d\n",Lc->data);
            Lc->next=T_O(La,Lb->next,Lc->next);
        }else if(Lb==NULL&&La!=NULL){
            Lc=La;
            //printf("此时Lc的值为%d\n",Lc->data);
            Lc->next=T_O(La->next,Lb,Lc->next);
        }else{ return Lc;}
        return Lc;
    }
    /*
    if(La==NULL){
        Lc=Lb;
        return;
    }else if(Lb==NULL){
        Lc=La;
        return;
    }
    */
    LNode pa=La;
    //printf("pa的值为%d\n",pa->data);
    LNode pb=Lb;
   // printf("pb的值为%d\n",pb->data);
    
    if(pa->data<=pb->data){
        Lc=(LNode)malloc(sizeof(List));
        Lc=pa;
        Lc->next=T_O(La->next,Lb,Lc->next);
    }else{
        Lc=(LNode)malloc(sizeof(List));
        Lc=pb;
        Lc->next=T_O(La,Lb->next,Lc->next);
    }
    return Lc;
}

int main()
{
    LNode La;
    int la[]={3,1,3,5};
    int lb[]={3,2,4,6};
    LNode Lb;
    LNode Lc;
    La=InitList(La,la,1);
    printf("La值为:");
   dispList(La);
    Lb=InitList(Lb,lb,1);
    printf("Lb值为:");
    dispList(Lb);
    Lc=T_O(La,Lb,Lc);
    printf("La与Lb合并后Lc值为:");
    dispList(Lc);
   // printf("Hello");
    return 0;
}

附上在线测试链接