王道课后习题2.3.8：找出两个链表的公共结点

题目描述：

给定两个单链表，编写算法找出两个链表的公共结点。

算法思想：

核心代码：

#include <stdio.h>
#include <algorithm>

typedef struct LNode//如果不在这里加LNode，结构体内的LNode*就会报错
{
    int data;
    LNode* next;
}LNode;

int Length(LNode* L)//注意：这里之前写成了int Length(LNode* &L)用的引用。
//这样的话，head1和head2最后都会变成NULL。难怪执行不对。
{
    int k=0;
    while(L!=NULL)
    {
        k++;
        L=L->next;
    }
    return k;
}

LNode* Find_Pubilc_Node(LNode* &head1,LNode* &head2)//不带头结点
{
    int len1=Length(head1);
    int len2=Length(head2);
    int longlen,shortlen;
    LNode *longlist,*shortlist;
    if(len1>len2)
    {
        longlen=len1;//或者不用记录longlen,shortlen。在这里直接算出差值k。
        shortlen=len2;
        longlist=head1;
        shortlist=head2;
    }
    else
    {
        longlen=len2;
        shortlen=len1;
        longlist=head2;
        shortlist=head1;
    }
    int k=longlen-shortlen;
    while((k--)!=0)//这里忘记--了
    {
        longlist=longlist->next;
    }
    //while(longlist&&shortlist&&longlist->data!=shortlist->data)这里不是找相同的值
    while(longlist!=NULL)
    {
        if(longlist==shortlist)
            return longlist;
        else
        {
            longlist=longlist->next;
            shortlist=shortlist->next;
        }
    }

    return NULL;
}

LNode* HeadInsert(LNode* &head)
{
    int x;
    scanf("%d",&x);
    head->next=NULL;
    while(x!=999)
    {
        LNode *p;
        p=(LNode *)malloc(sizeof(LNode));
        p->data=x;
        p->next=head->next;
        head->next=p;
        scanf("%d",&x);
    }

    return head->next;
    //return head;
    /*根据需要返回
    1.return head带头结点的链表
    2.return head->next不带头结点的链表
    */
}
LNode* TailInsert(LNode* &head)
{
    LNode *r=head;
    int x;
    scanf("%d",&x);
    while(x!=999)
    {
        LNode *p;
        p=(LNode *)malloc(sizeof(LNode));
        p->data=x;
        r->next=p;
        r=r->next;
        scanf("%d",&x);
    }
    r->next=NULL;//记得这句
    return head->next;
    //return head;
}

void TailInsert_PublicNode(LNode* &head1,LNode* &head2)
{
    printf("L1:\n");
    LNode *r1=head1;
    int x;
    scanf("%d",&x);
    while(x!=999)
    {
        LNode *p;
        p=(LNode *)malloc(sizeof(LNode));
        p->data=x;
        r1->next=p;
        r1=r1->next;
        scanf("%d",&x);
    }

    printf("L2:\n");
    LNode *r2=head2;

    scanf("%d",&x);
    while(x!=999)
    {
        LNode *p;
        p=(LNode *)malloc(sizeof(LNode));
        p->data=x;
        r2->next=p;
        r2=r2->next;
        scanf("%d",&x);
    }
    printf("public:\n");
    scanf("%d",&x);
    while(x!=999)
    {
        LNode *p;
        p=(LNode *)malloc(sizeof(LNode));
        p->data=x;
        r1->next=p;
        r1=r1->next;
        r2->next=p;
        r2=r2->next;
        scanf("%d",&x);
    }

    r1->next=NULL;//记得这句
    r2->next=NULL;//记得这句

    //return head;
}

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

int main()
{
    LNode *head1,*head2;//如果只是LNode* head，头插的时候就会出错。这里需要动态申请一个结点才行。
    head1=(LNode*)malloc(sizeof(LNode));//凡是结点，都需要动态申请，而不是仅仅一个指针
    head2=(LNode*)malloc(sizeof(LNode));
    TailInsert_PublicNode(head1,head2);//因为建链表返回的是head->next。
    PrintList(head1->next);
    printf("\n");
    PrintList(head2->next);//PrintList(head)，head并没有改变。
    LNode* p=Find_Pubilc_Node(head1->next,head2->next);
    printf("\n");
    PrintList(p);
    return 0;
}