判断两个链表是否有公共节点？

Question

#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;
}

请问要怎么调用才能输出链表的公共节点？

Answer 1

修改如下，供参考：

#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->next = NULL;
        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 ptr1 = L1->next, ptr2 = L2->next;
    int d = 0, step = len1 - len2;
    if (step > 0) {
        for (d = 0; d < step; d++)
            ptr1 = ptr1->next;
    }
    else {
        for (d = 0; d < -1 * step; d++)
            ptr2 = ptr2->next;
    }
    while (ptr1 != NULL)
    {
        if (ptr1 == ptr2) //找到第一个公共节点返回 
            return ptr1;
        ptr1 = ptr1->next;
        ptr2 = ptr2->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++;
        }
        printf("\n");
    }
    return len;
}
int main() {
    LinkList L1, L2, L3, p1, p2;
    InitList(L1);
    InitList(L2);
    InitList(L3);
    CreateTail(L1);
    int len1 = PrintList(L1);
    printf("L1-len is:%d\n", len1);
    CreateTail(L2);
    p1 = L1->next->next;
    p2 = L2->next;
    while (p2->next)
        p2 = p2->next;
    p2->next = p1->next->next; //公共点为 L1 的第四个元素
    int len2 = PrintList(L2);
    printf("L2-len is:%d\n", len2);
    p1 = SearchCommon(L1, L2, len1, len2);
    if (p1 != NULL)
        printf("the first intersection node is %d", p1->data);
    else
        printf("there is no insection node between the two list");
    return 0;
}