判斷兩個連結串列是否相交併找出第一個相交節點

判斷兩個連結串列是否相交併找出第一個相交節點

引言:連結串列問題是資料結構中的常見問題,對於面試、筆試都有很大的作用,那麼如何判斷兩個連結串列是否相交併找出第一個相交節點?

分析:找出兩個連結串列的交點首先就是判斷連結串列是否相交,那麼首先來看什麼是兩個連結串列相交?

一、什麼是連結串列相交?

資料結構的連結串列定義中儲存了指向下一個元素的指標,如果當兩個連結串列有交點時,即兩個連結串列會在各自連結串列中的某個結點,同時指向了相同的下一個結點,即如下圖所示:
這裡寫圖片描述
圖中可以看出,從連結串列一和連結串列二的相交處開始,後續結點都為相同結點。

此外,還要記住以下幾點:

①相交的兩個單連結串列要麼均有環,要麼都沒有環

②一個有環的單連結串列和一個無環的單連結串列不可能相交

二、怎麼判斷兩個連結串列是否相交?

先判斷兩個單連結串列是否有環,若一個有環,一個無環,則肯定不相交,剩下的情況要麼兩個單連結串列都有環,要麼都沒有環。

兩個單連結串列都為無環情況:

方法一:根據上圖連結串列相交,可知,最簡單的方法是判斷兩個連結串列的最後一個結點是否相等,如果相等,那麼這兩個連結串列就相交。時間複雜度為O(len1 len2)。

方法二:依次判斷第一個連結串列中的每個節點是否在第二個連結串列中出現,若出現,則兩個連結串列相交。時間複雜度為O(len1*len2),該時間複雜度比較大。

方法三:如下圖所示
這裡寫圖片描述

首先遍歷第一個連結串列,找到它的尾部,並讓它指向第二個連結串列的頭部,然後兩個連結串列就合二為一,成為了一個新的組合連結串列,現在只需要判斷新的連結串列是否含有環即可。因為第二個連結串列頭部在環上,所以從第二個連結串列開始遍歷判斷是否有環,可以減少時間複雜度,減少的為連結串列A的長度,最終時間複雜度為O(len1 len2)。

方法四:首先將第一個連結串列所有節點地址進行hash排序,並建立hash表,然後將第二個連結串列中每個節點地址進行判斷,看是否在hash表中存在,弱國存在,則兩個連結串列相交,時間複雜度為O(len1 len2)。

兩個單連結串列都為有環情況(三種情況):

①第一個相交節點在環開始之前:
這裡寫圖片描述
②第一個相交節點在環入口處:
這裡寫圖片描述
③第一個相交節點在環內:
這裡寫圖片描述
前兩種相交的節點在環之前,和環開始的地方,對於他們來說第一次相交的節點是相同的。

但對於第三種情況,即相交在環內的情況來看,如圖,對於連結串列一來說,P1點是第一次相交的節點,對於連結串列二來說P2點是第一次相交的節點。

判斷相交方法:

方法一:將其中任意一個連結串列的環打破,即讓尾節點指向null(記住儲存原本應當指向的位置),然後判斷第二個連結串列是否含有環,若第二個連結串列中無環,則兩個連結串列相交,否則不相交(記住,兩個連結串列本身就是有環的,一個有環的連結串列和一個無環的連結串列不存在相交點)。
這裡寫圖片描述
方法二:利用判斷單連結串列是否有環的方法,對連結串列一使用兩個快慢指標進行判斷是否有環,兩個指標的碰撞點即在環上,那麼判斷連結串列二的環上是否包含該碰撞點就可以判斷兩個連結串列是否相交了。

三、怎麼找到兩個連結串列的第一個相交節點?

兩個單連結串列都為無環情況:

方法一:依次判斷第一個連結串列中的每個節點是否在第二個連結串列中出現,第一個出現在連結串列二中的節點即為第一個相交節點。

方法二:人為構造環,如下圖
這裡寫圖片描述
首先遍歷第一個連結串列,找到它的尾部,並讓它指向第二個連結串列的頭部,然後兩個連結串列就合二為一,成為了一個新的組合連結串列,找到新連結串列的環入口節點,即為兩個連結串列相交的第一個節點。

方法三:分別遍歷兩個連結串列,記錄連結串列長度len1,len2。用兩個指標指向兩個連結串列的頭部,讓長度較長的連結串列先走|len1-len2|步,然後兩個指標共同走,當兩個指標相等時,即為第一個相交連結串列。

兩個單連結串列都為有環情況:

方法一:第一個相交節點在環之前和環入口節點的情況的方法,如上述方法三。

方法二:第一個相交節點在環內的情況方法如下,分別找到連結串列一和連結串列二的環入口節點,各自的環入口節點即為各自第一次相交的節點。即為下圖中的P1和P2節點。
這裡寫圖片描述

四、總結

如果兩個單連結串列相交,那麼一定是都有環或者都沒有環,不存在一個有環一個沒環的兩個連結串列相交。所以,判斷連結串列相交,首先判斷兩個連結串列是否有環。

根據有環和無環的情況,分別處理,判斷出是否相交,進而找出第一個相交節點。