鏈表總結

2019-11-08 01:43:29

字體：大中小

來源：轉載

供稿：網友

1.快速找到未知長度單鏈表的中間節點

a.初級算法：

從頭遍歷到末尾，再次從頭遍歷到中間處。O（L+L/2) =O（3L/2）

b.高級算法：

利用快慢指針原理：設置兩個指針fast 和mid，都指向單鏈表的頭節點。其中fast的移動速度是mid的2倍。當fast指向末尾節點的時候，mid正好就在中間了。O(L/2)

public static int void getMidNode(MyList L){ MyList fast,mid; fast = L.head; mid = L.head; while(fast.next != null){ if(fast.next.next!=null){ fast = fast.next.next; mid = mid.next; } else fast = fast.next; } return mid.data;}

2.判斷鏈表中是否有環

利用快慢指針原理，最后快慢指針相撞。

1. 有環時求環的長度 記錄碰撞點P，slow、fast指針從該點出發，再次碰撞所走過的操作數就是環的長度s。 2. 找出環的連接點 有定理：碰撞點p到連接點的距離=頭指針到連接點的距離，因此，分別從頭結點，碰撞點開始走（相同的速度），相遇的地方就是連接點。證明：

假設單鏈表的總長度為L，頭結點到環入口的距離為a，環入口到快慢指針相遇的結點距離為x，環的長度為r，慢指針總共走了s步，則快指針走了2s步。另外，快指針要追上慢指針的話快指針至少要在環里面轉了一圈多(假設轉了n圈加x的距離)，得到以下關系：s = a + x;2s = a + nr + x;=>a + x = nr;=>a = nr - x;由上式可知：若在頭結點和相遇結點分別設一指針，同步(單步)前進，則最后一定相遇在環入口結點，搞定！附圖：

這里寫圖片描述

3. 求帶環鏈表的長度 問題2中已經求出連接點距離頭指針的長度，加上問題1中求出的環的長度，二者之和就是帶環單鏈表的長度

3.判斷兩個無環鏈表是否相交，并找出相交點

a.轉換為判斷是否有環。將第一個鏈表的表尾部指向第二條鏈表的頭部，再從第二個鏈表的頭部進行遍歷（如果有環，那么第二條的頭節點就一定在環上）。

這里寫圖片描述

b.遍歷兩條鏈表，并判斷最后一個節點是否相等，因為，如果相交，那么最后一個節點一定相同。

這里寫圖片描述

c.判斷兩個鏈表中是否存在地址一致的節點，就可以知道是否相交了。可以對第一個鏈表的節點地址進行hash排序，建立hash表，然后針對第二個鏈表的每個節點的地址查詢hash表，如果它在hash表中出現，則說明兩個鏈表有共同的結點。這個方法的時間復雜度為：O(max(len1+len2)；但同時還得增加O(len1)的存儲空間存儲哈希表。這樣減少了時間復雜度，增加了存儲空間。以鏈表節點地址為值，遍歷第一個鏈表，使用Hash保存所有節點地址值，結束條件為到最后一個節點（無環）或Hash中該地址值已經存在（有環）。

判斷出兩個鏈表相交后，找出其相交點。

法1：假設第一條和第二條鏈表的長度為len1，len2，然后找出較長的鏈表，并讓其從|len1- len2|，開始遍歷，逐個比較兩個鏈表的值。法2：將兩個鏈表壓棧，并比較兩個棧出來的數據，直到兩個數據不同時，就可以判斷相交點。

問題的延伸：如果原來的兩個鏈表中有環怎么處理？ a.創建第一個鏈表的地址hash，直到所有節點都存入（終結條件就是添加新的hash時，hash表中已經存在了）。遍歷第二個鏈表，并hash，判斷是否在表中。 b.分三種情況：兩條head都不在環上，都在環上，有一個在環上，這三種方式都可以用快慢指針進行判斷。這里寫圖片描述

3.用兩個棧實現鏈表

方法一：創建兩個棧S1,S2,始終維護S1作為存儲空間，S2作為出棧的臨時緩沖區，出完棧后，將數據倒回S1。方法二：關鍵思路是，在有需要的時候再將S2的數據倒回S1，在連續性出棧，提高效率。入棧時判斷S1是否為空，如果為空，將S2中的數據倒回S1,再壓棧；出棧時，判斷S2數據是否為空，如果不空，則直接出棧。方法三：入棧時，將數據壓入S1，出棧時，判斷S2是否為空，如果為空，則將S1的數據倒入S2；如果S2不空，則直接從S2中出棧數據。總結：方法三的效率最高，但是也有問題，比如連續性的壓棧，導致S1的空間耗盡，但是S2的空間不能拿來使用。這里寫圖片描述