扩展1：链表1 步长为1， 链表2步长为2 ，如果有环且相交则肯定相遇，否则不相交
list1 head: p1
list2 head: p2
while( p1 != p2 && p1 != NULL && p2 != NULL )
{
p1 = p1->next;
if ( p2->next )
p2 = p2->next->next;
else
p2 = p2->next;
}
if ( p1 == p2 && p1 && p2) //相交
else //不相交
扩展2：在判断是否相交的过程中要分别遍历两个链表，同时记录下各自长度。
Node* step( Node* p, Node* q)
{
if ( !p || !q )
return NULL;
int pLen = 1;
int qLen = 1;
bool result = false;
while( p->next )
{
pLen++, p = p->next;
}
while( q->next )
{
qLen++, q = q->next;
}
result = ( p == q );
if ( result )
{
int steps = abs( pLen - qLen);
Node* head = pLen > qLen ? p : q;
while ( steps ) //对齐处理
{
head = head->next, steps--;
Node* head = pLen > qLen ? p : q;
while ( steps ) //对齐处理
{
head = head->next, steps--;
}
pLen > qLen ? p = head : q = head;
while ( p != q )
{
p = p->next, q = q->next;
}
reutrn p;
}
return NULL;
}
[重要提醒]对本篇资料有疑问，请到论坛讨论，尽量使文章准确无误>>>
[版权声明]BSD爱好者乐园站内文章，如来源不是互联网，则均系原创或翻译之作，可随意转载，或以此为基础进行演译，但务必以链接形式注明原始出处和作者信息，否则属于侵权行为。另对本站转载他处文章，俱有说明，如有侵权请联系本人，本人将会在第一时间删除侵权文章。
TAG: 编程之美 读书笔记