王道課後習題2.3.22：兩個連結清單的共同字尾

題目描述：

帶頭結點的單連結清單，尋找兩個連結清單的共同字尾的起始位置。

算法思想：

雙指針法

核心代碼：

//雙指針法
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* Find_Pubilc_Node_2(LNode* &head1,LNode* &head2)//不帶頭結點
{
    int len1=Length(head1);
    int len2=Length(head2);
    LNode *longlist,*shortlist;
    int dist=0;
    if(len1>len2)
    {
        dist=len1-len2;
        longlist=head1;
        shortlist=head2;
    }
    else
    {
        dist=len2-len1;
        longlist=head2;
        shortlist=head1;
    }
    while((dist--)!=0)//這裡忘記--了
    {
        longlist=longlist->next;
    }
    while(longlist!=NULL)
    {
        if(longlist==shortlist)
            return longlist;
        else
        {
            longlist=longlist->next;
            shortlist=shortlist->next;
        }
    }
    return NULL;
}

LNode* Find_Pubilc_Node_3(LNode* &head1,LNode* &head2)//不帶頭結點
{
    int len1=Length(head1);
    int len2=Length(head2);
    LNode *p,*q;
    p=head1->next;
    q=head2->next;
    while(len1>len2)//3>1,移動兩次
    {
        p=p->next;
        len1--;
    }
    while(len1<len2)
    {
        q=q->next;
        len2--;
    }
    while(p!=NULL&&p!=q)
    {
        p=p->next;
        q=q->next;
    }
    return p;

}
           

完整代碼：

#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* Find_Pubilc_Node_2(LNode* &head1,LNode* &head2)//不帶頭結點
{
    int len1=Length(head1);
    int len2=Length(head2);
    LNode *longlist,*shortlist;
    int dist=0;
    if(len1>len2)
    {
        dist=len1-len2;
        longlist=head1;
        shortlist=head2;
    }
    else
    {
        dist=len2-len1;
        longlist=head2;
        shortlist=head1;
    }
    while((dist--)!=0)//這裡忘記--了
    {
        longlist=longlist->next;
    }
    while(longlist!=NULL)
    {
        if(longlist==shortlist)
            return longlist;
        else
        {
            longlist=longlist->next;
            shortlist=shortlist->next;
        }
    }
    return NULL;
}

LNode* Find_Pubilc_Node_3(LNode* &head1,LNode* &head2)//不帶頭結點
{
    int len1=Length(head1);
    int len2=Length(head2);
    LNode *p,*q;
    p=head1->next;
    q=head2->next;
    while(len1>len2)//3>1,移動兩次
    {
        p=p->next;
        len1--;
    }
    while(len1<len2)
    {
        q=q->next;
        len2--;
    }
    while(p!=NULL&&p!=q)
    {
        p=p->next;
        q=q->next;
    }
    return p;

}




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_3(head1->next,head2->next);
    printf("\n");
    PrintList(p);
    return 0;
}