1997216lsy推薦於 2019-10-06

方法一：直接法

直接判斷第一個連結串列的每個結點是否在第二個連結串列中，時間複雜度為O（len1*len2），耗時很大

方法二：利用計數

如 果 兩個連結串列相交，則兩個連結串列就會有共同的結點；而結點地址又是結點唯一標識。因而判斷兩個連結串列中是否存在地址一致的節點，就可以知道是否相交了。可以對第一 個連結串列的節點地址進行hash排序，建立hash表，然後針對第二個連結串列的每個節點的地址查詢hash表，如果它在hash表中出現，則說明兩個連結串列有共 同的結點。這個方法的時間複雜度為：O（max（len1+len2）；但同時還得增加O（len1）的儲存空間儲存雜湊表。這樣減少了時間複雜度，增加 了儲存空間。

以連結串列節點地址為值，遍歷第一個連結串列，使用Hash儲存所有節點地址值，結束條件為到最後一個節點（無環）或Hash中該地址值已經存在（有環）。

再遍歷第二個連結串列，判斷節點地址值是否已經存在於上面建立的Hash表中。

這個方面可以解決題目中的所有情況，時間複雜度為O（m+n），m和n分別是兩個連結串列中節點數量。由於節點地址指標就是一個整型，假設連結串列都是在堆中動態建立的，可以使用堆的起始地址作為偏移量，以地址減去這個偏移量作為Hash函式

方法三

兩個沒有環的連結串列相交於一節點，則在這個節點之後的所有結點都是兩個連結串列所共有的。如果它們相交，則最後一個結點一定是共有的，則只需要判斷最後一個結點是否相同即可。時間複雜度為O（len1+len2）。對於相交的第一個結點，則可求出兩個連結串列的長度，然後用長的減去短的得到一個差值 K，然後讓長的連結串列先遍歷K個結點，然後兩個連結串列再開始比較。還可以這樣：其中一個連結串列首尾相連，檢測另外一個連結串列是否存在環，如果存在，則兩個連結串列相交，而檢測出來的依賴環入口即為相交的第一個