給出兩個(gè)單向鏈表的頭指針，而兩個(gè)鏈表都可能帶環(huán)溯职，判斷這兩個(gè)鏈表是否相交精盅，并且給出他們相交的第一個(gè)節(jié)點(diǎn)
1)判斷鏈表是否存在環(huán)
設(shè)置兩個(gè)鏈表指針(fast, slow)，初始值都指向鏈表頭結(jié)點(diǎn)谜酒，然后連個(gè)指針都往前走叹俏，不同的是slow每次前進(jìn)一步，fast每次前進(jìn)兩步僻族，如果存在環(huán)粘驰，兩個(gè)指針必定相遇。
(2)若鏈表有環(huán)述么，找到環(huán)的入口點(diǎn)
當(dāng)fast與slow相遇時(shí)蝌数，slow還沒(méi)走完鏈表，而fast已經(jīng)在環(huán)內(nèi)循環(huán)了n圈了度秘，假設(shè)slow在相遇前走了s步顶伞，則fast走了2s步，設(shè)環(huán)長(zhǎng)為r，有2s=s+nr唆貌，即s=nr.
由上圖可知a+x=s, x+y=r滑潘，而我們的目標(biāo)是找到a的位置。設(shè)上圖那個(gè)拱起的曲線的長(zhǎng)度為y锨咙，有a+x=s=nr=(n-1)r+r=(n-1)r+y+x众羡，則a=(n-1)r+y. 這個(gè)公式告訴我們，從鏈表頭和相遇點(diǎn)分別設(shè)一個(gè)指針蓖租，每次各走一步，這兩個(gè)指針必定相遇羊壹，且相遇的第一個(gè)點(diǎn)為環(huán)入口點(diǎn)蓖宦。
(3)若兩個(gè)鏈表都不存在環(huán)，找出兩個(gè)鏈表相交的第一個(gè)節(jié)點(diǎn)
- 將其中一個(gè)鏈表首尾相連油猫，判斷另一個(gè)鏈表是否存在環(huán)稠茂，如果存在，則兩個(gè)鏈表相交情妖，且找出來(lái)的環(huán)入口點(diǎn)即為相交的第一個(gè)點(diǎn)睬关。
- 首先遍歷兩個(gè)鏈表，記下兩個(gè)鏈表的長(zhǎng)度毡证，長(zhǎng)鏈表從起點(diǎn)先前進(jìn)len_max-len_min步电爹，然后兩個(gè)鏈表再一起前進(jìn)，每次一步料睛，相遇的第一個(gè)點(diǎn)即為相交的第一個(gè)點(diǎn)丐箩。
(4)若兩個(gè)鏈表都存在環(huán)，找出兩個(gè)鏈表相交的第一個(gè)節(jié)點(diǎn)
通過(guò)方法(1)我們能夠分別找出兩個(gè)鏈表的相遇點(diǎn)pos1, pos2恤煞，然后還是使用兩個(gè)指針fast和slow屎勘，都初始化為pos1，且fast每次前進(jìn)2步居扒，slow每次前進(jìn)1步概漱。若fast指針在遇到slow前，出現(xiàn)fast等于pos2或fast->next等于pos2喜喂，則說(shuō)明兩個(gè)鏈表相交瓤摧，否則不相交。若兩鏈表相交夜惭，我們可知pos2肯定是兩個(gè)鏈表的一個(gè)相交點(diǎn)姻灶，將這個(gè)點(diǎn)看做兩個(gè)鏈表的終止節(jié)點(diǎn)，使用(3)中的解法诈茧，即可找到兩個(gè)鏈表相交的第一個(gè)節(jié)點(diǎn)产喉。
