感謝azuryy提供《編程之美》3.6節“鏈表相交”擴展問題答案

（原博客地址：http://hi.baidu.com/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;

}

轉載于:https://www.cnblogs.com/bvbook/archive/2008/07/30/1256289.html

總結

以上是生活随笔為你收集整理的《编程之美》读书笔记（十）：“链表相交”扩展问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。