感谢azuryy提供《编程之美》3.6节“链表相交”扩展问题答案
(原博客地址:/azuryy/blog/item/18e85b02ec34a4094bfb51de.html)
扩展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--;
}
pLen > qLen ? p = head : q = head;
while ( p != q )
{
p = p->next, q = q->next;
}
reutrn p;
}
return NULL;
}