(链表)判断两个单链表是否存在交点

2.判断两个单链表是否存在交点,如果存在交点,则找到相交的一点。
(1)只需判断是否相交
用两个分别跑到单链表的未结点处,然后判断是否是同一个尾结点即可
(2)指出具体的相交的结点是什么
先统计两个单链表长度,然后让指针p指向较长的单链表,让指针q指向较短的单链表
让p指针提前出发,向后走差值步
此时p和q相较于交点的距离就一样,这此时再以同样的速度出发,看啥时候相遇即可
//1.先统计两个单链表的有效长度,然后让指针p指向较长的单链表,让指针
// q指向较短的单链表

int len1 = GetLength(plist1);
int len2 = GetLength(plist2);

Node* p = len1 >= len2 ? plist1 : plist2;
Node* q = len1 >= len2 ? plist2 : plist1;

//2.让p指针提前出发,向后走(两个单链表的长度差值)步
for (int i = 0; i < abs(len1 - len2); i++)
    p = p->next;

//3.此时p和q相较于相交点的距离就一样了,则此时再以同样的速
// 度出发,看啥时候相遇即可

while (p != q)
{
    p = p->next;
    q = q->next;
}

return p;//return q;
posted @ 2025-11-16 20:41  汉堡堡  阅读(5)  评论(0)    收藏  举报