如何求两个链表的交点（就是公共节点）？

来源：百度知道 编辑：UC知道 时间：2024/07/02 06:01:06
如何求两个链表的交点（就是公共节点）？比如给出两个表的标头node* t1和node* t2，如何求出他们的公共节点？需要一定的速度，最好是在O(n2)(大O n平方)内求出来，也就是要比两个while循环这种做法时间复杂性更低，更快。
还有点问题，比如两个链表是这样的：
1 2 3 4 5 6 7 8 9 10
1 -3 -4 -5 -6 -7 -8 -9 -10
这样不就找不到了吗？
或者是
1 2 3 4 5 6 7 8
1 4 -4 -5 -6 -7 -8
不就也找不到了吗？
有办法解决吗？

/*
确切的说是求两个链表的第一个公共结点
因为链表相交成'Y'形,算法思想是先求出l1比
l2长多少或是短多少,然后将长的从头遍历差数个结点,
然后和短的一起遍历,直到相等
*/
Node* find(Node* head1,Node* head2)
{
Node *p1=head1,*p2=head2;
int m=0,n=0;
while(p1)//O(len1)
{
p1=p1->next;
m++;
}
while(p2)//O(len2)
{
p2=p2->next;
n++;
}
p1=head1;
p2=head2;
if(m>n)
{
for(i=0;i<m-n;i++)
p1=p1->next;
}
else
{
for(i=0;i<n-m;i++)
p2=p2->next;
}//O(abs(len1-len2))
while(p1!=p2)
{
p1=p1->next;
p2=p2->next;
}//O(min(len1,len2))
return p1;//合起来为O(2*len1+len2)或O(2*len2+len1)远小于O(len1*len2)
}