筆試算法題（27）：判斷單向連結清單是否有環并找出環入口節點 & 判斷兩棵二進制樹是否相等

出題：判斷一個單向連結清單是否有環，如果有環則找到環入口節點；

分析：

第一個問題：使用快慢指針（fast指針一次走兩步，slow指針一次走一步，并判斷是否到達NULL，如果fast==slow成立，則說明連結清單有環）；

第二個問題：fast與slow相遇時，slow一定還沒有走完一圈（反證法可證明）；

 示意圖

A為起始點，B為環入口點，C為相遇點，則a1=|AB|表示起始點到換入口的距離，a2=|CB|表示相遇點到環入口點的距離，s1=|AB|+|BC|表示slow指針走的長度，s2表示fast指針走的長度，C=|BCB|表示環的長度

由于fast的速度是slow的2倍，是以相遇的時候走過的長度也是2倍

s2=2*s1=a1+N*C+(s1-a1)

(1)

N表示fast在環中走的圈數，化解(1)得到：

s1=N*C

(2)

找到a1和a2的關系：

a2=C-(s1-a1)

(3)

将(2)代入(3)得到：

a1=a2+(N-1)*C

(4)

是以如果指針m從起始點A出發，指針n從相遇點C出發，n繞行(N-1)圈環之後最終跟m指針在B點相遇

解題：

出題：判斷兩棵二進制樹是否相等（左右子樹不能交叉比較）；

分析：使用遞歸實作，在樹的K層，有2^K 個節點，是以會進行(2^K)*2次調用，是以時間複雜度為O(N)；