注册 登录
编程论坛 数据结构与算法

请问判断两个链表是否有公共节点?

Gloria_zhang 发布于 2022-01-24 19:50, 1630 次点击
程序代码:

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;
bool InitList(LinkList &L){
    L=(LinkList)malloc(sizeof(LNode));
    L->next=NULL;
    return true;
}
LinkList CreateTail(LinkList &L){
    LNode *r=L;
    int x;
    scanf("%d",&x);
    while(x!=9999){
        LNode *s=(LNode *)malloc(sizeof(LNode));
        s->data=x;
        s->next=r->next;
        r->next=s;
        r=s;
        scanf("%d",&x);
    }
    return L;
}
LinkList SearchCommon(LinkList L1,LinkList L2,int len1,int len2){
     LinkList longlist,shortlist;
     int d=0;
     if(len1>len2){
         longlist=L1->next;
         shortlist=L2->next;
        d=len1-len2;
     }
     else{
         longlist=L2->next;
         shortlist=L1->next;
         d=len2-len1;
     }
     while(d--) longlist=longlist->next;
     while(longlist!=NULL){
         if(longlist==shortlist){//找到第一个公共节点返回
            return longlist;
        }   
         else{
             longlist=longlist->next;
             shortlist=shortlist->next;
         }
     }
     return NULL;
}
int PrintList(LinkList L){
    LNode *p=L->next;
    int len=0;
    if(p==NULL) printf("enpty.");
    else{
        printf("list is:");
        while(p!=NULL){
            printf("%4d",p->data);
            p=p->next;
            len++;
        }
    }
    return len;
}
int main(){
    LinkList L1,L2,L3;
    InitList(L1);
    InitList(L2);
    InitList(L3);
    CreateTail(L1);
    int len1=PrintList(L1);
    printf("\nlen is:%d",len1);
    CreateTail(L2);
    int len2=PrintList(L2);
    printf("\nlen is:%d",len2);
    L3=SearchCommon(L1,L2,len1,len2);
    printf("\n");
    printf("%d",L3);
    return 0;
}

请问要怎么调用才能输出链表的公共节点?
1 回复
1