相交鏈表
- Part I、何謂相交？
- 1、 文字決議
- 2、圖形決議
- Part II、 進階！
- 方法一
- 方法二
- Part III、總結
Part I、何謂相交？
1、 文字決議
我們知道，鏈表可以分為單鏈表和雙鏈表，前者有唯一的next指標指向下一個節點，而后者在此基礎上新增了一個prev指標指向它的前一個節點，這是區別，但是共同點是，無論是next指標還是prev指標，它們指向的物件具有唯一性，這也是鏈表作為線性表最大的特點之一，
當我們知道鏈表的線性特性后，我們可以再來想：一個指標指向的節點確實具有唯一性，但是指向這個節點的指標并不具有唯一性，換句話說，可以同時有一個、兩個甚至更多的指標同時指向一個節點（不過本篇文章我們只討論一個，其余可以類推），當出現這種情況時，我們可以說，這寫指標所在的鏈表是相交的，交點就是這個唯一指向的節點，
2、圖形決議
看完鏈表相交的文字決議，如果還有點懵懵的，不妨看看下面的圖形示意：
可以看到，相交鏈表的圖中，上下兩個鏈表的第二個節點同時都指向同一個三號節點，因此說它們是相交的，
Part II、 進階！
我們剛剛看了兩鏈表在相交前節點數相等的情況，但事實上兩鏈表長度是未知的，相交節點前的總結點數也是未知的，
方法一
如果節點長度相等，那么我們可以采取兩鏈表同時從頭到尾遍歷的方式，當兩個遍歷指標相等且不為NULL時，代表相交節點找到了，
如果不相等，那么我們可以就需要一個m*n的嵌套回圈遍歷兩個鏈表，什么意思？直接來看代碼：
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
//方法一、O(m*n)的遍歷
struct ListNode* cur1 = headA, *cur2 = headB;
while(cur1)
{
cur2 = headB;
while(cur2)
{
if(cur1 == cur2 && cur1)
{
return cur1;
}
cur2 = cur2->next;
}
cur1 = cur1->next;
}
return NULL;
}
外回圈由cur1控制，內回圈由cur2控制，cur1每走一步，cur2就需要從頭到尾遍歷一次鏈表，在遍歷的程序中尋找非空的共同結點，
這種方法非常簡單易懂且好想，但唯一的問題就是：時間復雜度為O(m*n)，消耗較大，有沒有什么效率更高的解法？
方法二
我們在前面的討論中強調了的某一點非常重要：兩個鏈表的長度，
為什么不能采取兩鏈表同時從頭到尾遍歷的方式？因為它們的長度不同，為了走到相交的節點需要移動的次數不同，
那么，突破點就來了:只要讓這兩個鏈表在相交節點前的節點數相同就行了！
為什么這么說？
還是因為鏈表的線性特性——
如果兩個鏈表相交了，那么相交節點后的部分是完全相同的，唯一不同的就是相交節點前的那些，因此可以斷定：兩個鏈表的長度差存在于相交節點前，
于是我們可以采取一種方法，就是：給兩個鏈表中較短的那一個頭插一些結點使其和長鏈表的長度相同，不過這也帶來了O(N)的記憶體消耗，
所以我們不妨換一個思路：
讓長的鏈表先遍歷n個結點，其中n就是兩個鏈表的長度差，然后再讓兩個鏈表同時遍歷，不就可以達到目的了嗎？
此時兩個遍歷的指標就是站在同一起跑線了，因為它們距離相交節點的距離是相同的，
代碼實作一下：
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
//方法二、求出兩鏈表的長度差x，讓長的鏈表先走x，然后兩鏈表再一起走，找出相同的節點
struct ListNode* cur1 = headA, *cur2 = headB;
int len1 = 0, len2 = 0;
while(cur1)
{
cur1 = cur1->next;
len1++;
}//求鏈表A的長度
while(cur2)
{
cur2 = cur2->next;
len2++;
}//求鏈表B的長度
struct ListNode* longList = headA, *shortList = headB;
if(len2 > len1)
{
longList = headB;
shortList = headA;
}//找出長的那個鏈表
int n = abs(len1-len2);//求出長度差
while(n--)
{
longList = longList->next;//讓長的鏈表先走n個結點
}
while(longList && shortList)//遍歷，找到相同的節點
{
if(longList == shortList)
return longList;
longList = longList->next;
shortList = shortList->next;
}
return NULL;
}
Part III、總結
一個鏈表相交的問題可以有多種思路，各有特色也各有優點，不過這里還是比較看好最后實作的這種，以O(n)的時間復雜度和O(1)的空間復雜度很好地解決了相交的問題！
如果對鏈表相交還有其他見解，歡迎評論區指教哦！
歡迎關注博主，定期分享各種題解！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/292034.html
標籤：其他
下一篇：一看就懂的IP協議！！！