判断两个普通单向链表是否有交点（如何快速找到这个交点）

如果两个链表有交点那么代表这两个链表是一个Y型的链表

Y型的链表代表这两的链表的尾地址是相同的

如何能快速的的找到这个交点的位置呢？

首先我们可以确定的是两个普通单向链表的长度 当这两个普通单向链表存在交点时那么代表交点向后的结点都重合那么我们就可以通过长度的差值来确定交点的位置

若两个链表的长度差值为K那么我们 先定义两个指针让他们分别指向两个链表的头结点先让长的链表的指针先走K步，然后这两个链表的指针开始同步向前走直到连个指针指向相同的地址这时我们就找到了 交点的位置

typedef struct node_t
{
    int data;//data
    struct node_t *next; //next
}node;

node* find_node(node *head1, node *head2)
{
    //链表带头节点
    if(head1==NULL || head2==NULL)
    {
        return NULL;//如果有为空的链表，肯定是不相交的
    }
    node *p1, *p2;
    p1 = head1;
    p2 = head2;
    int len1 = 0;
    int len2 =0;
    int diff = 0;
    while(p1->next!=NULL)
    {
        p1 = p1->next;
        len1++;
    }
    while(p2->next!=NULL)
    {
        p2 = p2->next;
        len2++;
    }
    if(p1 != p2) //如果最后一个节点不相同,返回NULL
    {
        return NULL;
    }
    diff = abs(len1 - len2);
    if(len1 > len2)
    {
        p1 = head1;
        p2 = head2;
    }
    else
    {
        p1 = head2;
        p2 = head1;
    }
    for(int i=0; i<diff; i++)
    {
        p1 = p1->next;
    }
    while(p1 != p2)
    {
        p1 = p1->next;
        p2 = p2->next;
    }
    return p1;
}
 

最后

以上就是烂漫小霸王为你收集整理的判断两个普通单向链表是否有交点（如何快速找到这个交点）的全部内容，希望文章能够帮你解决判断两个普通单向链表是否有交点（如何快速找到这个交点）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。