问题描述

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

算法思想

我们从单链表的定义中可以发现每一个结点只有一个next域，那么从第一个公共结点开始，后面所有的结点都应该是重合的，形状应该类似与倒Y型（“>-”）。既然如此，那么对两条单链表同时开始遍历，只要它们的指针同时指向同一个结点（即：两指针相等）时不就找到公共结点了吗？
但在实现的时候，应该注意到，两张链表在等长的情况下，同时开始遍历，指针必然可以同时指向公共结点；可是如果不等长的话，同时遍历是无法同时指向公共结点的。
这里总结下思想核心

• 分别求出两条单链表的长度len1和len2以及长度之差len；
• 让LongPoint指针指向长度较长的单链表，让ShortPoint指针指向长度较短的单链表；
• 对齐两条单链表的表尾，让长链表先遍历 len个结点；
• 长短单链表同时开始遍历，直到指针LongPoint与指针ShortPoint指向同一个结点（相等）时为止。

算法描述

LNode* FindCommon(LNode* head1, LNode* head2)
{
    int len1=ListLength(head1);//求链表1的长度
    int len2=ListLength(head2);//求链表2的长度
    int len;            //长短单链表长度差
    LNode *LongPoint;   //指向长链表
    LNode *ShortPoint;  //指向短炼表
    //判断长短链表
    if(len1>len2){
        len=len1-len2;
        LongPoint=head1->next;
        ShortPoint=head2->next;
    }else{
        len=len2-len1;
        LongPoint=head2->next;
        ShortPoint=head1->next;
    }
    //长链表先遍历长短链表长度差个结点
    while(len--){
        LongPoint=LongPoint->next;
    }
    //长短链表同时开始遍历
    while(LongPoint!=NULL){
        if(LongPoint==ShortPoint){
            return LongPoint;
        }
        else{
            LongPoint=LongPoint->next;
            ShortPoint=ShortPoint->next;
        }
    }
    return NULL;

}

具体代码见附件。

附件

#include<stdio.h>
#include<stdlib.h>

typedef int ElemType;
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

LinkList CreatList(LNode*);
LNode* FindCommon(LNode*,LNode*);
int ListLength(LNode*);
void Print(LNode*);

int main(int argc, char* argv[])
{
    LNode *head1;
    head1=(LNode*)malloc(sizeof(LNode));
    head1->next=NULL;
    head1=CreatList(head1);
    printf("Head1: ");
    Print(head1);

    int i=4;
    LNode *p=head1;
    while(i--){
        p=p->next;
    }

    LNode *head2;
    head2=(LNode*)malloc(sizeof(LNode));
    head2=CreatList(head2);

    LNode *r=head2->next;
    while(r->next){
        r=r->next;
    }
    r->next=p;

    printf("head2: ");
    Print(head2);

    LNode *head;
    head=(LNode*)malloc(sizeof(LNode));
    head->next=NULL;
    head->next=FindCommon(head1, head2);
    printf("head:  ");
    Print(head);

    return 0;
}
//尾插法建立单链表
LinkList CreatList(LNode *head)
{
    LNode *r=head;
    LNode *L;
    ElemType x;
    scanf("%d",&x);
    while(x!=999){
        L=(LNode*)malloc(sizeof(LNode));
        L->data=x;
        r->next=L;
        r=L;
        scanf("%d",&x);
    }
    r->next=NULL;
    return head;
}
//寻找公共结点
LNode* FindCommon(LNode* head1, LNode* head2)
{
    int len1=ListLength(head1);
    int len2=ListLength(head2);
    int len;
    LNode *LongPoint;
    LNode *ShortPoint;
    if(len1>len2){
        len=len1-len2;
        LongPoint=head1->next;
        ShortPoint=head2->next;
    }else{
        len=len2-len1;
        LongPoint=head2->next;
        ShortPoint=head1->next;
    }
    while(len--){
        LongPoint=LongPoint->next;
    }
    while(LongPoint!=NULL){
        if(LongPoint==ShortPoint){
            return LongPoint;
        }
        else{
            LongPoint=LongPoint->next;
            ShortPoint=ShortPoint->next;
        }
    }
    return NULL;

}
//求单链表长度
int ListLength(LNode *head)
{
    LNode *p=head;
    int count=0;
    while(p){
        ++count;
        p=p->next;
    }
    return count;
}
//打印全部结点
void Print(LNode *head)
{
    LNode *p=head->next;
    while(p){
        printf("%4d",p->data);
        p=p->next;
    }
        printf("
");
}

注：
本源代码的主函数部分中，首先创建了单链表1，然后遍历单链表1四个结点，接着让单表2的尾结点的next域指向单链表1的第四个结点，从而形成两条具有公共结点的单链表。
故此代码中最大的Bug就是因为此单链表都是自己创建的，所以公共结点在哪儿一开始就已经知道了。然后睁着眼睛说了半天瞎话……