寻找两个链表共同结点

寻找两个链表共同结点

这个相同结点是指,中间某个结点的next指针,指向同一片区域,并不是仅仅元素值相同

解决步骤
1、使用两个指针,先求出L1,L2的长度
2、先用一个指针p,将长链表,遍历到和短链表相同长度(p每次向后移动)
3、两个指针同时一起向后移动,直到指向相同结点位置

实现代码

#include 
#include 
#include


typedef int Elemtype;

//单链表

typedef struct LNode
{
    Elemtype data;//存放数据
    struct LNode *next; //指向LNode的一个指针

} LNode,*LinkList; //相当于取别名,LNode代表一个节点,LinkList代表整个单链表(指向LNode的一个指针)

void PrintList(LinkList L)
{
    LinkList p;
    p=L->next;//找到头指针指向节点,开始遍历
    printf("链表元素如下：\n");
    while(p!=NULL)
    {
        printf("%d ",p->data);
        p=p->next;
    }
    printf("\n");
}

int GetLen(LinkList L)
{
    LinkList p;
    p=L;
    int len=0;
    while(p!=NULL)
    {
        p=p->next;
        len++;
    }
    return len;
}

//尾插法
LinkList List_TailInsert(LinkList L)
{
    int x;
    L=(LinkList)malloc(sizeof(LNode));
    LNode *r=L,*s;
    scanf("%d",&x);

    while(x!=9999)
    {
        s=(LNode*)malloc(sizeof(LNode));
        s->data=x;
        r->next=s;
        r=s;
        scanf("%d",&x);
    }
    r->next=NULL;
    return L;
}
//创建共同结点
void Create_Common(LinkList L1,LinkList L2)
{
    LNode *p=L1->next,*q=L2->next;
    while(p->next!=NULL)
    {
        p=p->next;
    }
    while(q->next!=NULL)
    {
        q=q->next;
    }
    int x;
    printf("请输入共同结点元素值:\n");//这里也可以用一个while循环多创建几个相同结点
    scanf("%d",&x);
    LNode *s=(LNode*)malloc(sizeof(LNode));
    s->data=x;
    p->next=s;
    q->next=s;
    s->next=NULL;
}
//寻找共同结点
LinkList Search_lst_Common(LinkList L1,LinkList L2)
{
    int len1=GetLen(L1),len2=GetLen(L2);
    int dist;
    LinkList longList,shortList;
    //比较链表长短
    if(len1>len2)
    {
        longList=L1->next;
        shortList=L2->next;
        dist=len1-len2;
    }
    else
    {
        longList=L2->next;
        shortList=L1->next;
        dist=len2-len1;
    }
    //将长链表遍历到和短链表相同长度
    while(dist--)
    {
        longList=longList->next;
    }
    while(longList!=NULL)
    {
        if(longList==shortList)return longList;//找到共同结点
        else
        {
            longList=longList->next;
            shortList=shortList->next;
        }
    }
    return NULL;//没找到返回NULL
}


int main()
{
    LinkList L1,L2;//使用头插法 这里的L就是一个头指针
    printf("请输入链表元素,输入9999表示结束\n");
    L1=List_TailInsert(L1); // 1 2 3 4
    PrintList(L1);
    printf("请输入链表元素,输入9999表示结束\n");
    L2=List_TailInsert(L2);
    PrintList(L2);
    //创建共同结点
    Create_Common(L1,L2);
    printf("找到共同结点\n");
    LNode *p=Search_lst_Common(L1,L2);//共同结点
    printf("当前结点值为:%d",p->data);
    return 0;
}