給出兩個單向鏈表的頭指針，而兩個鏈表都可能帶環(huán)，判斷這兩個鏈表是否相交，并且給出他們相交的第一個節(jié)點
1)判斷鏈表是否存在環(huán)
設置兩個鏈表指針(fast, slow)，初始值都指向鏈表頭結(jié)點，然后連個指針都往前走，不同的是slow每次前進一步，fast每次前進兩步，如果存在環(huán)，兩個指針必定相遇。
(2)若鏈表有環(huán)，找到環(huán)的入口點
當fast與slow相遇時，slow還沒走完鏈表，而fast已經(jīng)在環(huán)內(nèi)循環(huán)了n圈了，假設slow在相遇前走了s步，則fast走了2s步，設環(huán)長為r，有2s=s+nr，即s=nr.
由上圖可知a+x=s, x+y=r，而我們的目標是找到a的位置。設上圖那個拱起的曲線的長度為y，有a+x=s=nr=(n-1)r+r=(n-1)r+y+x，則a=(n-1)r+y. 這個公式告訴我們，從鏈表頭和相遇點分別設一個指針，每次各走一步，這兩個指針必定相遇，且相遇的第一個點為環(huán)入口點。
(3)若兩個鏈表都不存在環(huán)，找出兩個鏈表相交的第一個節(jié)點
- 將其中一個鏈表首尾相連，判斷另一個鏈表是否存在環(huán)，如果存在，則兩個鏈表相交，且找出來的環(huán)入口點即為相交的第一個點。
- 首先遍歷兩個鏈表，記下兩個鏈表的長度，長鏈表從起點先前進len_max-len_min步，然后兩個鏈表再一起前進，每次一步，相遇的第一個點即為相交的第一個點。
(4)若兩個鏈表都存在環(huán)，找出兩個鏈表相交的第一個節(jié)點
通過方法(1)我們能夠分別找出兩個鏈表的相遇點pos1, pos2，然后還是使用兩個指針fast和slow，都初始化為pos1，且fast每次前進2步，slow每次前進1步。若fast指針在遇到slow前，出現(xiàn)fast等于pos2或fast->next等于pos2，則說明兩個鏈表相交，否則不相交。若兩鏈表相交，我們可知pos2肯定是兩個鏈表的一個相交點，將這個點看做兩個鏈表的終止節(jié)點，使用(3)中的解法，即可找到兩個鏈表相交的第一個節(jié)點。
