数据结构：判断两个单链表是否相交

categories:

• 数据结构

题目要求

判断两个单链表是否相交，如果相交则返回第一个相交的节点，如果没有相交则返回NULL

算法

1、先求两个链表长度的差值，让长的链表指针先走这个差值，如下图让plist1先走到p位置

2、完成步骤1后，让两个链表的指针同步向后走，每走一步判断两个节点是否相等，如果相等则直接返回这个节点，如果走到NULL，则两个链表不相交

C代码

LinkList IsIntersect(LinkList plist1, Linklist plist2)
{
    if (plist1 == NULL || plist2 == NULL)
    {
        return NULL;
    }
    if (ListEmpty(plist1) || ListEmpty(plist2))//空链表
    {
        return NULL;
    }

    int len1 = GetLength(plist1);
    int len2 = GetLength(plist2);
    LinkList p = plist1, q = plist2;

    if (len1 > len2)// 长链表走差值
    {
        for (int i = 0; i < len1 - len2; i++)
        {
            p = p->next;
        }
    }
    else
    {
        for (int i = 0; i < len2 - len1; i++)
        {
            q = q->next;
        }
    }

    while (p != NULL)//两个指针同步走
    {
        p = p->next;
        q = q->next;
        if (p == q)
        {
            return p;
        }
    }
    return NULL;
}