判斷兩個單鏈表是否相交以及相交的情況下求第一個相交節(jié)點，兩個鏈表可以有環(huán)，也可以無環(huán)。因此我們可以從以下幾個步驟分析：
- 判斷一個單鏈表是否存在環(huán)路，如果無環(huán)，返回null，反之，返回入環(huán)節(jié)點。
- 如果兩個單鏈表均無環(huán)，進入相應的子程序，如果無相交，返回null，反之，返回第一個相交節(jié)點。
- 如果一個有環(huán)，一個無環(huán)，進入相應的子程序，如果無相交，返回null，反之，返回第一個相交節(jié)點。
- 如果兩個單鏈表均有環(huán)，進入相應的子程序，如果無相交，返回null，反之，返回第一個相交節(jié)點。
接下來，我們結合圖片以及相應的理論對這四個小問題求解。
-
判斷一個單鏈表是否存在環(huán)路
如下圖所示，如果單鏈表存在環(huán)路，則只可能是圖一所示的結構，請讀者自行收起野馬般的思路，類似圖二的結構是不存在的。
正確的的有環(huán)鏈表上圖中的入環(huán)節(jié)點為節(jié)點2。
錯誤的有環(huán)鏈表接下來，我們分析一下判斷單鏈表是否有環(huán)，如果有環(huán)，返回入環(huán)節(jié)點的思路。
首先，有兩種解決方案，一種情況算法空間復雜度為O(N)，另一種空間復雜度O(1)，讀者可以根據(jù)不同的情形擇優(yōu)選取。
第一種：使用HashSet，因為HashSet只能容納不重復的元素，所以從頭遍歷鏈表，將經(jīng)過的每一個節(jié)點都加進去，如果發(fā)現(xiàn)有重復，則直接返回第一個重復的節(jié)點，就是入環(huán)節(jié)點。如果沒有重復，說明鏈表無環(huán)，返回null。
很明顯，這個算法空間復雜度為O(N)，在此不展示代碼，因為較為簡單，讀者有興趣可以自己嘗試，接下來講述第二種方法，空間復雜度為O(1)。第二種：使用快慢指針。快指針一次走兩步，慢指針一次走一步，很明顯，當快指針遇到null走不動的時候，就可以確定鏈表無環(huán)，直接返回null。
如果鏈表存在環(huán)路，可以得到一個結論是快指針在有限的步數(shù)內(nèi)肯定會追上慢指針并且相遇（敲黑板），讀者可以自行畫圖嘗試，是一個很容易觀察出來的結論。
下一步，在快慢指針相遇的一刻，將快指針指向頭節(jié)點，然后讓快慢指針同時走，并都走一步，注意，這里是都走一步并且保持同步。下面，見證奇跡的時刻到了，當快慢節(jié)點再次相遇時，二者此時都指向入環(huán)節(jié)點，也就是兩個指針肯定都會在入環(huán)節(jié)點處首次相遇。這個結論可以用數(shù)學歸納法證明，筆者不羅列出證明過程，讀者記住這個結論就可以編碼了，并且肯定正確。下面是代碼。
/** * 判斷一個鏈表是否有環(huán)，如果有環(huán)返回入環(huán)節(jié)點，如果無環(huán)，返回null。 * 步驟： * ①準備兩個快慢指針，一個一次走一步，一個一次走兩步，如果有環(huán)，兩個指針肯定會相遇，如果快指針走到了null，則代表無環(huán)； * ②當兩個指針相遇后，將快指針指向頭節(jié)點，然后兩個指針每次都同時走一步，當兩個指針相等時，就到了鏈表的入環(huán)節(jié)點，返回即可。 * @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; } //達到這一步之后，兩個指針相遇 //接著將快指針指向頭節(jié)點 fast = head; //二者同時走相同的步數(shù)，肯定會在入環(huán)節(jié)點處相遇，相遇后返回即可 while(fast != slow) { fast = fast.next; slow = slow.next; } return fast; }至此，第一步，判斷鏈表是否有環(huán)，已經(jīng)結束。
-
兩個無環(huán)鏈表的相交節(jié)點
這里直接說明一個結論，如果兩個無環(huán)鏈表相交，那么它們倆的最后一個節(jié)點必然相等，也就是被兩個鏈表共享。如果兩個鏈表的最后一個節(jié)點不相等，那么兩個鏈表一定不想等。
如下圖說明了兩個無環(huán)列表的相交情況，下圖一是正確的相交情況，下圖二是不可能存在的相交情況。正確的無環(huán)鏈表相交錯誤的情況：
錯誤的無環(huán)鏈表相交因此，得到上面的分析，我們來梳理一下求解第一個相交節(jié)點的思路。
首先，得到分別得到兩個鏈表的長度length1、length2和兩個鏈表的最后一個節(jié)點end1、end2。如果兩個end節(jié)點不相等，直接返回null。
如果end相等，則計算兩個鏈表的長度之差，準備兩個指針分別指向等于head1和head2，讓指向長鏈表的指針先走長度之差個步數(shù)。舉個例子，如果兩個鏈表長度之差為20，則先讓指向長鏈表的指針走20步，接著讓兩個指針同步走，兩個指針第一次相遇的地方，就是兩個鏈表的第一個公共節(jié)點。
至此，判斷兩個無環(huán)鏈表的相交節(jié)點的思路已經(jīng)介紹完畢，下面看代碼：
/** * 返回兩個無環(huán)鏈表的第一個相交節(jié)點。 * 步驟： * ①遍歷兩個鏈表，分別得到長度和最后一個節(jié)點length1,end1;length2,end2； * ②如果兩個鏈表相交，end一定相同，否則，不相交，直接返回null。 * ③確定兩個鏈表長度的差值，讓長的鏈表先走差值這么大的步數(shù)，然后兩個鏈表同時走，相遇的時候就是第一個相交節(jié)點。 * @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并不是真實的長度，因為長度沒有意義，要得到的是二者的差值 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; //以上注釋的一段代碼跟以下的代碼等效，下面的代碼復用了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)鏈表的相交情況
這里直接說明結論，一個有環(huán)鏈表和一個無環(huán)鏈表不可能存在相交節(jié)點。讀者可以自行在草稿紙上畫，如果還存在疑問，請繼續(xù)往下讀文章。
-
兩個有環(huán)鏈表的相交節(jié)點
如下圖所示，兩個有環(huán)鏈表的位置關系只能有以下三種：不相交，第一種相交，第二種相交。
兩個有環(huán)鏈表可能存在的位置關系下面進行思路分析：
先獲取兩個鏈表的入環(huán)節(jié)點loopNode1和loopNode2，如果兩鏈表的入環(huán)節(jié)點相等，則為圖二所示的位置關系。如果兩個鏈表的入環(huán)節(jié)點不相等，則是圖一或圖三的位置關系。
先談兩個入環(huán)節(jié)點相等，對應于圖二所示的關系，其獲取相交節(jié)點的方式幾乎與獲取兩個無環(huán)鏈表相交節(jié)點的方式幾乎一模一樣。不一樣的一點是：無環(huán)鏈表需遍歷到end獲得length之間的差值，而圖二所示情況只遍歷到入環(huán)節(jié)點及l(fā)oopNode1或loopNode2處獲得length的差值即可。獲得length之間的差值后，得到相交節(jié)點與noLoop函數(shù)的邏輯一樣。
對于兩個入環(huán)節(jié)點不相等的情況，可能對應于圖一不相交，也可能是對應于圖三相交。那么如何將二者區(qū)分？方式就是從第一個鏈表的入環(huán)節(jié)點loopNnode1開始遍歷，如果在回到自身之前遇到了loopNode2，那么就是第三種情況，如果沒遇到，就是第一種不相交的情況。對于圖三相交的情況，直接返回兩個入環(huán)節(jié)點之一即可，因為兩個入環(huán)節(jié)點都是第一個相交的節(jié)點，只不過是針對不同的鏈表而言的。
至此，獲取兩個有環(huán)鏈表第一個相交節(jié)點的思路已經(jīng)介紹完畢，下面是代碼：
/** * 返回兩個有環(huán)鏈表的第一個相交節(jié)點。 * 步驟： * ①判斷兩種有環(huán)鏈表的相交情況，可能有不相交，第一種相交，第二種相交（在相應的圖上）； * ②如果兩個鏈表的入環(huán)節(jié)點相等，則為第一種相交情況； * ③針對第一種相交情況，其實與無環(huán)鏈表相交理論基本上一致，只不過計算長度的時候無環(huán)是到end，有環(huán)則是到入環(huán)節(jié)點； * ④如果不相等，則為不相交或者第二種相交情況； * ⑤此時把loopNode1一直往下走，如果在回到自己之前，沒有遇到loopNode2，則為兩個鏈表不相交， * 否則相交，直接返回loopNode1或loopNode2即可，因為這兩個都是第一個相交節(jié)點，只不過是針對不同鏈表而言的。 * @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é)點的過程已經(jīng)全部介紹完畢，下面是主函數(shù)的代碼：
/** * 得到兩個鏈表相交的主函數(shù)，該函數(shù)分為以下幾個步驟： * ①判斷兩個鏈表有環(huán)無環(huán)的情況，一個有環(huán)和一個無環(huán)的節(jié)點不可能相交； * ②得到兩個無環(huán)鏈表的相交節(jié)點； * ③得到兩個有環(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)鏈表，將進入無環(huán)鏈表求相交節(jié)點的函數(shù)。 if(loopNode1 == null && loopNode2 == null) { return noLoop(head1, head2); } //如果都是有環(huán)鏈表，將進入有環(huán)鏈表求相交節(jié)點的函數(shù)。 if(loopNode1 != null && loopNode2 != null) { return bothLoop(head1, head2); } //如果一個有環(huán)一個無環(huán)，直接返回null，因為不存在相交的可能性。 return null; }自己在main函數(shù)中寫測試用例即可，其中Node類就是普通的鏈表Node類，包含value和next指針。
Github鏈接：獲取兩鏈表第一個相交節(jié)點聲明：由于筆者寫完后沒有用過多的測試用例去測試，如果存在漏洞，歡迎批評與指正。
