思想：
這道題目其實思想上很簡單，就是讓兩個鏈表保持在同一起跑線上，一起往后遍歷，最終找到兩者指向地址相同的結點，這就是公共結點，詳情請看以下代碼，分為三個步驟，
代碼實作：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode* Alen = headA;
struct ListNode* Blen = headB;
int la = 0;
int lb = 0;
//1、計算兩個鏈表的長度
while(Alen)
{
la++;
Alen = Alen->next;
}
while(Blen)
{
lb++;
Blen = Blen->next;
}
//2、比較兩個鏈表的長度，將長的鏈表走兩個鏈表長度的差值，保證兩者在同一起跑線去向后遍歷
struct ListNode* longList = headA;
struct ListNode* shortList = headB;
if(la<lb)
{
longList = headB;
shortList = headA;
}
int gap = abs(la-lb);
while(gap--)
{
longList = longList->next;
}
//3、比較兩個鏈表指向的地址是否相同，如相同，則為公共結點
while(longList)
{
//比較長鏈表與短鏈表指向的地址是否相同，相同則回傳此時的結點
if(longList == shortList)
{
return longList;
}
//不相同就繼續向下一個結點遍歷
longList = longList->next;
shortList = shortList->next;
}
return NULL;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/262207.html
標籤：其他
上一篇：洛谷P1184 高手之在一起