判斷兩個單鏈表是否相交以及相交的情況下求第一個相交節(jié)點(diǎn)烹吵，兩個鏈表可以有環(huán)惧眠，也可以無環(huán)打颤。因此我們可以從以下幾個步驟分析：
- 判斷一個單鏈表是否存在環(huán)路暴拄，如果無環(huán)，返回null编饺，反之乖篷，返回入環(huán)節(jié)點(diǎn)。
- 如果兩個單鏈表均無環(huán)反肋，進(jìn)入相應(yīng)的子程序那伐，如果無相交，返回null，反之罕邀，返回第一個相交節(jié)點(diǎn)畅形。
- 如果一個有環(huán)，一個無環(huán)诉探，進(jìn)入相應(yīng)的子程序日熬，如果無相交，返回null肾胯，反之竖席，返回第一個相交節(jié)點(diǎn)。
- 如果兩個單鏈表均有環(huán)敬肚，進(jìn)入相應(yīng)的子程序毕荐，如果無相交，返回null艳馒，反之憎亚，返回第一個相交節(jié)點(diǎn)。
接下來弄慰，我們結(jié)合圖片以及相應(yīng)的理論對這四個小問題求解第美。
-
判斷一個單鏈表是否存在環(huán)路
如下圖所示，如果單鏈表存在環(huán)路陆爽，則只可能是圖一所示的結(jié)構(gòu)什往，請讀者自行收起野馬般的思路，類似圖二的結(jié)構(gòu)是不存在的慌闭。
正確的的有環(huán)鏈表上圖中的入環(huán)節(jié)點(diǎn)為節(jié)點(diǎn)2别威。
錯誤的有環(huán)鏈表接下來，我們分析一下判斷單鏈表是否有環(huán)驴剔，如果有環(huán)兔港，返回入環(huán)節(jié)點(diǎn)的思路。
首先仔拟，有兩種解決方案，一種情況算法空間復(fù)雜度為O(N)飒赃，另一種空間復(fù)雜度O(1)利花，讀者可以根據(jù)不同的情形擇優(yōu)選取。
第一種：使用HashSet载佳，因?yàn)镠ashSet只能容納不重復(fù)的元素炒事，所以從頭遍歷鏈表，將經(jīng)過的每一個節(jié)點(diǎn)都加進(jìn)去蔫慧，如果發(fā)現(xiàn)有重復(fù)挠乳，則直接返回第一個重復(fù)的節(jié)點(diǎn)，就是入環(huán)節(jié)點(diǎn)。如果沒有重復(fù)睡扬，說明鏈表無環(huán)盟蚣，返回null。
很明顯卖怜，這個算法空間復(fù)雜度為O(N)屎开，在此不展示代碼，因?yàn)檩^為簡單马靠，讀者有興趣可以自己嘗試奄抽，接下來講述第二種方法，空間復(fù)雜度為O(1)甩鳄。第二種：使用快慢指針逞度。快指針一次走兩步妙啃，慢指針一次走一步档泽，很明顯，當(dāng)快指針遇到null走不動的時候彬祖，就可以確定鏈表無環(huán)茁瘦，直接返回null。
如果鏈表存在環(huán)路储笑，可以得到一個結(jié)論是快指針在有限的步數(shù)內(nèi)肯定會追上慢指針并且相遇（敲黑板）甜熔，讀者可以自行畫圖嘗試，是一個很容易觀察出來的結(jié)論突倍。
下一步腔稀，在快慢指針相遇的一刻，將快指針指向頭節(jié)點(diǎn)羽历，然后讓快慢指針同時走焊虏，并都走一步，注意秕磷，這里是都走一步并且保持同步诵闭。下面，見證奇跡的時刻到了澎嚣，當(dāng)快慢節(jié)點(diǎn)再次相遇時疏尿，二者此時都指向入環(huán)節(jié)點(diǎn)，也就是兩個指針肯定都會在入環(huán)節(jié)點(diǎn)處首次相遇易桃。這個結(jié)論可以用數(shù)學(xué)歸納法證明褥琐，筆者不羅列出證明過程，讀者記住這個結(jié)論就可以編碼了晤郑，并且肯定正確敌呈。下面是代碼贸宏。
/** * 判斷一個鏈表是否有環(huán)，如果有環(huán)返回入環(huán)節(jié)點(diǎn)磕洪，如果無環(huán)吭练，返回null。 * 步驟： * ①準(zhǔn)備兩個快慢指針褐鸥，一個一次走一步线脚，一個一次走兩步，如果有環(huán)叫榕，兩個指針肯定會相遇浑侥，如果快指針走到了null，則代表無環(huán)晰绎； * ②當(dāng)兩個指針相遇后寓落，將快指針指向頭節(jié)點(diǎn)，然后兩個指針每次都同時走一步荞下，當(dāng)兩個指針相等時伶选，就到了鏈表的入環(huán)節(jié)點(diǎn)，返回即可尖昏。 * @param head * @return */ private static Node getLoopNode(Node head) { if(head.next == null || head.next.next == null) { return null; } Node slow = head.next; Node fast = head.next.next; while(slow != fast) { if(fast.next == null || fast.next.next == null) { return null; } slow = slow.next; fast = fast.next.next; } //達(dá)到這一步之后仰税，兩個指針相遇 //接著將快指針指向頭節(jié)點(diǎn) fast = head; //二者同時走相同的步數(shù)，肯定會在入環(huán)節(jié)點(diǎn)處相遇抽诉，相遇后返回即可 while(fast != slow) { fast = fast.next; slow = slow.next; } return fast; }至此陨簇，第一步，判斷鏈表是否有環(huán)迹淌，已經(jīng)結(jié)束河绽。
-
兩個無環(huán)鏈表的相交節(jié)點(diǎn)
這里直接說明一個結(jié)論，如果兩個無環(huán)鏈表相交唉窃，那么它們倆的最后一個節(jié)點(diǎn)必然相等耙饰，也就是被兩個鏈表共享。如果兩個鏈表的最后一個節(jié)點(diǎn)不相等纹份，那么兩個鏈表一定不想等苟跪。
如下圖說明了兩個無環(huán)列表的相交情況，下圖一是正確的相交情況蔓涧，下圖二是不可能存在的相交情況削咆。正確的無環(huán)鏈表相交錯誤的情況：
錯誤的無環(huán)鏈表相交因此，得到上面的分析蠢笋，我們來梳理一下求解第一個相交節(jié)點(diǎn)的思路。
首先鳞陨，得到分別得到兩個鏈表的長度length1昨寞、length2和兩個鏈表的最后一個節(jié)點(diǎn)end1瞻惋、end2。如果兩個end節(jié)點(diǎn)不相等援岩，直接返回null歼狼。
如果end相等，則計算兩個鏈表的長度之差享怀，準(zhǔn)備兩個指針分別指向等于head1和head2羽峰，讓指向長鏈表的指針先走長度之差個步數(shù)。舉個例子添瓷，如果兩個鏈表長度之差為20梅屉，則先讓指向長鏈表的指針走20步，接著讓兩個指針同步走鳞贷，兩個指針第一次相遇的地方坯汤，就是兩個鏈表的第一個公共節(jié)點(diǎn)。
至此搀愧，判斷兩個無環(huán)鏈表的相交節(jié)點(diǎn)的思路已經(jīng)介紹完畢惰聂，下面看代碼：
/** * 返回兩個無環(huán)鏈表的第一個相交節(jié)點(diǎn)。 * 步驟： * ①遍歷兩個鏈表咱筛，分別得到長度和最后一個節(jié)點(diǎn)length1,end1;length2,end2搓幌； * ②如果兩個鏈表相交，end一定相同迅箩，否則溉愁，不相交，直接返回null沙热。 * ③確定兩個鏈表長度的差值叉钥，讓長的鏈表先走差值這么大的步數(shù)，然后兩個鏈表同時走篙贸，相遇的時候就是第一個相交節(jié)點(diǎn)投队。 * @param head1 * @param head2 * @return */ private static Node noLoop(Node head1, Node head2) { int length1 = 0; int length2 = 0; Node end1 = head1; Node end2 = head2; while(end1.next != null) { length1++; end1 = end1.next; } while (end2.next != null) { length2++; end2 = end2.next; } //這里得到的length1和length2并不是真實(shí)的長度，因?yàn)殚L度沒有意義爵川，要得到的是二者的差值 int difference = Math.abs(length1-length2); // 讓長度長的先走一段距離 // for(int i = 0; i < difference; i++) { // if(length1 > length2) { // head1 = head1.next; // } // else { // head2 = head2.next; // } // } // // 共同走一段距離 // while(head1 != head2) { // head1 = head1.next; // head2 = head2.next; // } // return head1; //以上注釋的一段代碼跟以下的代碼等效敷鸦，下面的代碼復(fù)用了end1和end2，使用end1來代表長的寝贡，end2來代表短的扒披，這樣就不用在循環(huán)中判斷了 end1 = length1 > length2 ? head1 : head2; end2 = end1 == head1 ? head2 : head1; for(int i = 0; i < difference; i++) { end1 = end1.next; } while(end1 != end2) { end1 = end1.next; end2 = end2.next; } return end1; } -
有環(huán)鏈表和無環(huán)鏈表的相交情況
這里直接說明結(jié)論，一個有環(huán)鏈表和一個無環(huán)鏈表不可能存在相交節(jié)點(diǎn)圃泡。讀者可以自行在草稿紙上畫碟案，如果還存在疑問，請繼續(xù)往下讀文章颇蜡。
-
兩個有環(huán)鏈表的相交節(jié)點(diǎn)
如下圖所示价说，兩個有環(huán)鏈表的位置關(guān)系只能有以下三種：不相交辆亏，第一種相交，第二種相交鳖目。
兩個有環(huán)鏈表可能存在的位置關(guān)系下面進(jìn)行思路分析：
先獲取兩個鏈表的入環(huán)節(jié)點(diǎn)loopNode1和loopNode2扮叨，如果兩鏈表的入環(huán)節(jié)點(diǎn)相等，則為圖二所示的位置關(guān)系领迈。如果兩個鏈表的入環(huán)節(jié)點(diǎn)不相等彻磁，則是圖一或圖三的位置關(guān)系。
先談兩個入環(huán)節(jié)點(diǎn)相等狸捅，對應(yīng)于圖二所示的關(guān)系衷蜓，其獲取相交節(jié)點(diǎn)的方式幾乎與獲取兩個無環(huán)鏈表相交節(jié)點(diǎn)的方式幾乎一模一樣。不一樣的一點(diǎn)是：無環(huán)鏈表需遍歷到end獲得length之間的差值薪贫，而圖二所示情況只遍歷到入環(huán)節(jié)點(diǎn)及l(fā)oopNode1或loopNode2處獲得length的差值即可恍箭。獲得length之間的差值后，得到相交節(jié)點(diǎn)與noLoop函數(shù)的邏輯一樣瞧省。
對于兩個入環(huán)節(jié)點(diǎn)不相等的情況扯夭，可能對應(yīng)于圖一不相交，也可能是對應(yīng)于圖三相交鞍匾。那么如何將二者區(qū)分交洗？方式就是從第一個鏈表的入環(huán)節(jié)點(diǎn)loopNnode1開始遍歷，如果在回到自身之前遇到了loopNode2橡淑，那么就是第三種情況构拳，如果沒遇到，就是第一種不相交的情況梁棠。對于圖三相交的情況置森，直接返回兩個入環(huán)節(jié)點(diǎn)之一即可，因?yàn)閮蓚€入環(huán)節(jié)點(diǎn)都是第一個相交的節(jié)點(diǎn)符糊，只不過是針對不同的鏈表而言的凫海。
至此，獲取兩個有環(huán)鏈表第一個相交節(jié)點(diǎn)的思路已經(jīng)介紹完畢男娄，下面是代碼：
/** * 返回兩個有環(huán)鏈表的第一個相交節(jié)點(diǎn)行贪。 * 步驟： * ①判斷兩種有環(huán)鏈表的相交情況，可能有不相交模闲，第一種相交建瘫，第二種相交（在相應(yīng)的圖上）； * ②如果兩個鏈表的入環(huán)節(jié)點(diǎn)相等尸折，則為第一種相交情況啰脚； * ③針對第一種相交情況，其實(shí)與無環(huán)鏈表相交理論基本上一致实夹，只不過計算長度的時候無環(huán)是到end橄浓，有環(huán)則是到入環(huán)節(jié)點(diǎn)晾咪； * ④如果不相等，則為不相交或者第二種相交情況贮配； * ⑤此時把loopNode1一直往下走，如果在回到自己之前塞赂，沒有遇到loopNode2泪勒，則為兩個鏈表不相交， * 否則相交宴猾，直接返回loopNode1或loopNode2即可圆存，因?yàn)檫@兩個都是第一個相交節(jié)點(diǎn)，只不過是針對不同鏈表而言的仇哆。 * @param head1 * @param head2 * @return */ private static Node bothLoop(Node head1, Node head2) { Node loopNode1 = getLoopNode(head1); Node loopNode2 = getLoopNode(head2); if(loopNode1 == loopNode2) { int length1 = 0; int length2 = 0; Node end1 = head1; Node end2 = head2; while(end1.next != loopNode1) { length1++; end1 = end1.next; } while (end2.next != loopNode2) { length2++; end2 = end2.next; } //這里得到的length1和length2并不是到end的長度沦辙，而是到loopNode的長度 int difference = Math.abs(length1-length2); end1 = length1 > length2 ? head1 : head2; end2 = end1 == head1 ? head2 : head1; for(int i = 0; i < difference; i++) { end1 = end1.next; } while(end1 != end2) { end1 = end1.next; end2 = end2.next; } return end1; } else { Node temp = loopNode1.next; while(temp != loopNode1) { if(temp == loopNode2) { return loopNode1; //or return loopNode2; } temp = temp.next; } return null; } } -
總結(jié)
通過以上幾個步驟，求兩鏈表第一個相交節(jié)點(diǎn)的過程已經(jīng)全部介紹完畢讹剔，下面是主函數(shù)的代碼：
/** * 得到兩個鏈表相交的主函數(shù)油讯，該函數(shù)分為以下幾個步驟： * ①判斷兩個鏈表有環(huán)無環(huán)的情況，一個有環(huán)和一個無環(huán)的節(jié)點(diǎn)不可能相交延欠； * ②得到兩個無環(huán)鏈表的相交節(jié)點(diǎn)陌兑； * ③得到兩個有環(huán)鏈表的相交節(jié)。 * @param head1 * @param head2 * @return */ public static Node getIntersectNode(Node head1, Node head2) { if(head1 == null || head2 == null) { return null; } Node loopNode1 = getLoopNode(head1); Node loopNode2 = getLoopNode(head2); //如果都是無環(huán)鏈表由捎，將進(jìn)入無環(huán)鏈表求相交節(jié)點(diǎn)的函數(shù)兔综。 if(loopNode1 == null && loopNode2 == null) { return noLoop(head1, head2); } //如果都是有環(huán)鏈表，將進(jìn)入有環(huán)鏈表求相交節(jié)點(diǎn)的函數(shù)狞玛。 if(loopNode1 != null && loopNode2 != null) { return bothLoop(head1, head2); } //如果一個有環(huán)一個無環(huán)软驰，直接返回null，因?yàn)椴淮嬖谙嘟坏目赡苄浴? return null; }自己在main函數(shù)中寫測試用例即可心肪，其中Node類就是普通的鏈表Node類锭亏，包含value和next指針。
Github鏈接：獲取兩鏈表第一個相交節(jié)點(diǎn)聲明：由于筆者寫完后沒有用過多的測試用例去測試蒙畴，如果存在漏洞贰镣，歡迎批評與指正。
