如果兩個單向鏈表相交，一定是形成Y字形，而不會是X字形。基于這個想法，可以判斷兩鏈表是否相交。

代碼 NODE*?FindNode(NODE*?pHead1,?NODE*?pHead2)
{
????NODE*?p1?=?pHead1;
????NODE*?p2?=?pHead2;
????int?i?=?1,?j?=?1,?k?=?0,?f?=?0;

????if(pHead2?==?NULL?||?pHead2?==?NULL)
????{
????????return?NULL;
????}

????while(p1->next?!=?NULL)
????{
????????p1?=?p1->next;
????????i++;
????}

????while(p2->next?!=?NULL)
????{
????????p2?=?p2->next;
????????j++;
????}

????if(p1?!=?p2)
????{
????????return?NULL;????????//如果尾節點不同，直接返回NULL
????}
????else???????????????????//否則尋找第一個相同的節點
????{
????????p1?=?pHead1;????????????????//?1
????????p2?=?pHead2;????????????????//?2

????????f?=?fabs(i,?j);???//計算兩條鏈表長度的差
????????if(i?>?j)?????????//如果第一個鏈表比第二個長，第一個鏈表先向前移動f步
????????{
????????????for(k=0;?k<f;?k++)
????????????{
????????????????p1?=?p1->next;
????????????}
????????????while(p1?!=?p2)
????????????{
????????????????p1?=?p1->next;
????????????????p2?=?p2->next;
????????????}
????????????return?p1;
????????}
????????else
????????{
????????????for(k=0;?k<f;?k++)
????????????{
????????????????p2?=?p2->next;
????????????}
????????????while(p1?!=?p2)
????????????{
????????????????p1?=?p1->next;
????????????????p2?=?p2->next;
????????????}
????????????return?p1;
????????}
????}
}

?

轉載于:https://www.cnblogs.com/songQQ/archive/2009/12/01/1614661.html

總結

以上是生活随笔為你收集整理的如何判断两个单向链表是否有相交，并找出交点的全部內容，希望文章能夠幫你解決所遇到的問題。

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