本題來自左神《程序員代碼面試指南》“兩個單鏈表相交的一系列問題”題目。

題目

在本題中，單鏈表可能有環(huán)，也可能無環(huán)。給定兩個單鏈表的頭節(jié)點(diǎn) head1 和 head2，這兩個鏈表可能相交，也可能不相交。請實(shí)現(xiàn)一個函數(shù)，如果兩個鏈表相交，請返回相交的第一個節(jié)點(diǎn)；如果不相交，返回 null 即可。

要求：如果鏈表 1 的長度為 N，鏈表 2 的長度為 M，時(shí)間復(fù)雜度請達(dá)到 O(N+M)，額外空間復(fù)雜度請達(dá)到 O(1)。

題解

本題可以拆分成 三個子問題，每個問題都可以作為一道獨(dú)立的算法題，具體如下。

• 問題一：如何判斷一個鏈表是否有環(huán)，如果有，則返回第一個進(jìn)入環(huán)的節(jié)點(diǎn)，沒有則返回null。
• 問題二：如何判斷兩個無環(huán)鏈表是否相交，相交則返回第一個相交節(jié)點(diǎn)，不相交則返回null。
• 問題三：如何判斷兩個有環(huán)鏈表是否相交，相交則返回第一個相交節(jié)點(diǎn)，不相交則返回null。

注意：如果一個鏈表有環(huán)，另外一個鏈表無環(huán)，它們是不可能相交的，直接返回null。下面逐一分析每個問題。

問題一：如何判斷一個鏈表是否有環(huán)，如果有，則返回第一個進(jìn)入環(huán)的節(jié)點(diǎn)，沒有則返回 null。

如果一個鏈表沒有環(huán)，那么遍歷鏈表一定可以遇到鏈表的終點(diǎn)；如果鏈表有環(huán)，那么遍歷鏈表就永遠(yuǎn)在環(huán)里轉(zhuǎn)下去了。如何找到第一個入環(huán)節(jié)點(diǎn)，具體過程如下：

1．設(shè)置一個慢指針slow 和一個快指針fast。在開始時(shí)，slow 和fast 都指向鏈表的頭節(jié)點(diǎn)head。然后slow 每次移動一步，fast 每次移動兩步，在鏈表中遍歷起來。

2．如果鏈表無環(huán)，那么fast 指針在移動過程中一定先遇到終點(diǎn)，一旦fast 到達(dá)終點(diǎn)，說明鏈表是沒有環(huán)的，直接返回null，表示該鏈表無環(huán)，當(dāng)然也沒有第一個入環(huán)的節(jié)點(diǎn)。

3．如果鏈表有環(huán)，那么 fast 指針和 slow 指針一定會在環(huán)中的某個位置相遇，當(dāng)fast 和slow 相遇時(shí)，fast 指針重新回到head 的位置，slow 指針不動。接下來，fast 指針從每次移動兩步改為每次移動一步，slow 指針依然每次移動一步，然后繼續(xù)遍歷。

4．fast 指針和slow 指針一定會再次相遇，并且在第一個入環(huán)的節(jié)點(diǎn)處相遇。證明略。

注意：你也可以用哈希表完成問題一的判斷，但是不符合題目關(guān)于空間復(fù)雜度的要求。

問題一的具體實(shí)現(xiàn)請參看如下代碼中的 getLoopNode 方法。

public static Node getLoopNode(Node head) {if (head == null || head.next == null || head.next.next == null) {return null;}Node n1 = head.next; // n1 -> slowNode n2 = head.next.next; // n2 -> fastwhile (n1 != n2) {if (n2.next == null || n2.next.next == null) {return null;}n2 = n2.next.next;n1 = n1.next;}n2 = head; // n2 -> walk again from headwhile (n1 != n2) {n1 = n1.next;n2 = n2.next;}return n1; }

如果解決了問題一，我們就知道了兩個鏈表有環(huán)或者無環(huán)的情況。如果一個鏈表有環(huán)，另一個鏈表無環(huán)，那么這兩個鏈表是無論如何也不可能相交的。

能相交的情況就分為兩種，一種是兩個鏈表都無環(huán)，即問題二；另一種是兩個鏈表都有環(huán)，即問題三。

問題二：如何判斷兩個無環(huán)鏈表是否相交，相交則返回第一個相交節(jié)點(diǎn)，不相交則返回null。

如果兩個無環(huán)鏈表相交，那么從相交節(jié)點(diǎn)開始，一直到兩個鏈表終止的這一段，是兩個鏈表共享的。解決問題二的具體過程如下：

1．鏈表1 從頭節(jié)點(diǎn)開始，走到最后一個節(jié)點(diǎn)（不是結(jié)束），統(tǒng)計(jì)鏈表1 的長度記為len1，同時(shí)記錄鏈表1 的最后一個節(jié)點(diǎn)記為end1。

2．鏈表2 從頭節(jié)點(diǎn)開始，走到最后一個節(jié)點(diǎn)（不是結(jié)束），統(tǒng)計(jì)鏈表2 的長度記為len2，同時(shí)記錄鏈表2 的最后一個節(jié)點(diǎn)記為end2。

3．如果end1!=end2，說明兩個鏈表不相交，返回null 即可；如果end==end2，說明兩個鏈表相交，進(jìn)入步驟4 來找尋第一個相交節(jié)點(diǎn)。

4．如果鏈表1 比較長，鏈表1 就先走len1?len2 步；如果鏈表2 比較長，鏈表2 就先走len2?len1 步。然后兩個鏈表一起走，一起走的過程中，兩個鏈表第一次走到一起的那個節(jié)點(diǎn)就是第一個相交的節(jié)點(diǎn)。

例如：鏈表1 長度為100，鏈表2 長度為30，如果已經(jīng)由步驟3 確定了鏈表1 和鏈表2 一定相交，那么接下來，鏈表1 先走70 步，然后鏈表1 和鏈表2 一起走，它們一定會共同進(jìn)入第一個相交的節(jié)點(diǎn)。

問題二的具體實(shí)現(xiàn)，請參看如下代碼中的 noLoop 方法。

public static Node noLoop(Node head1, Node head2) {if (head1 == null || head2 == null) {return null;}Node cur1 = head1;Node cur2 = head2;int n = 0;while (cur1.next != null) {n++;cur1 = cur1.next;}while (cur2.next != null) {n--;cur2 = cur2.next;}if (cur1 != cur2) {return null;}cur1 = n > 0 ? head1 : head2;cur2 = cur1 == head1 ? head2 : head1;n = Math.abs(n);while (n != 0) {n--;cur1 = cur1.next;}while (cur1 != cur2) {cur1 = cur1.next;cur2 = cur2.next;}return cur1; }

問題三：如何判斷兩個有環(huán)鏈表是否相交，相交則返回第一個相交節(jié)點(diǎn)，不相交則返回null。

考慮問題三的時(shí)候，我們已經(jīng)得到了兩個鏈表各自的第一個入環(huán)節(jié)點(diǎn)，假設(shè)鏈表 1 的第一個入環(huán)節(jié)點(diǎn)記為loop1，鏈表2 的第一個入環(huán)節(jié)點(diǎn)記為loop2。以下是解決問題三的過程。

1．如果loop1==loop2，那么兩個鏈表的拓?fù)浣Y(jié)構(gòu)如圖2-8 所示。

這種情況下，我們只要考慮鏈表1 從頭開始到loop1 這一段與鏈表2 從頭開始到loop2 這一段，在那里第一次相交即可，而不用考慮進(jìn)環(huán)該怎么處理，這就與問題二類似，只不過問題二是把null 作為一個鏈表的終點(diǎn)，而這里是把loop1(loop2)作為鏈表的終點(diǎn)。但是判斷的主要過
程是相同的。

2．如果loop1!=loop2，兩個鏈表不相交的拓?fù)浣Y(jié)構(gòu)如圖2-9 所示。兩個鏈表相交的拓?fù)浣Y(jié)構(gòu)如圖2-10 所示。

如何分辨是這兩種拓?fù)浣Y(jié)構(gòu)的哪一種呢？進(jìn)入步驟3。
3．讓鏈表1 從loop1 出發(fā)，因?yàn)閘oop1 和之后的所有節(jié)點(diǎn)都在環(huán)上，所以 將來一定能回到 loop1。

• 如果回到loop1 之前 并沒有遇到loop2，說明兩個鏈表的拓?fù)浣Y(jié)構(gòu)如圖2-9 所示，也就是 不相交，直接返回 null；
• 如果回到loop1 之前 遇到了loop2，說明兩個鏈表的拓?fù)浣Y(jié)構(gòu)如圖2-10所示，也就是 相交。因?yàn)?loop1 和 loop2 都在兩條鏈表上，只不過loop1 是離鏈表1 較近的節(jié)點(diǎn)，loop2 是離鏈表2 較近的節(jié)點(diǎn)。所以，此時(shí)返回loop1 或loop2 都可以。

問題三的具體實(shí)現(xiàn)參看如下代碼中的 bothLoop 方法。

public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {Node cur1 = null;Node cur2 = null;if (loop1 == loop2) {cur1 = head1;cur2 = head2;int n = 0;while (cur1 != loop1) {n++;cur1 = cur1.next;}while (cur2 != loop2) {n--;cur2 = cur2.next;}cur1 = n > 0 ? head1 : head2;cur2 = cur1 == head1 ? head2 : head1;n = Math.abs(n);while (n != 0) {n--;cur1 = cur1.next;}while (cur1 != cur2) {cur1 = cur1.next;cur2 = cur2.next;}return cur1;} else {cur1 = loop1.next;while (cur1 != loop1) {if (cur1 == loop2) {return loop1;}cur1 = cur1.next;}return null;} }

附：完整代碼

package chapter_2_listproblem;public class Problem_11_FindFirstIntersectNode {public static class Node {public int value;public Node next;public Node(int data) {this.value = data;}}public static Node getIntersectNode(Node head1, Node head2) {if (head1 == null || head2 == null) {return null;}Node loop1 = getLoopNode(head1);Node loop2 = getLoopNode(head2);if (loop1 == null && loop2 == null) {return noLoop(head1, head2);}if (loop1 != null && loop2 != null) {return bothLoop(head1, loop1, head2, loop2);}return null;}public static Node getLoopNode(Node head) {if (head == null || head.next == null || head.next.next == null) {return null;}Node n1 = head.next; // n1 -> slowNode n2 = head.next.next; // n2 -> fastwhile (n1 != n2) {if (n2.next == null || n2.next.next == null) {return null;}n2 = n2.next.next;n1 = n1.next;}n2 = head; // n2 -> walk again from headwhile (n1 != n2) {n1 = n1.next;n2 = n2.next;}return n1;}public static Node noLoop(Node head1, Node head2) {if (head1 == null || head2 == null) {return null;}Node cur1 = head1;Node cur2 = head2;int n = 0;while (cur1.next != null) {n++;cur1 = cur1.next;}while (cur2.next != null) {n--;cur2 = cur2.next;}if (cur1 != cur2) {return null;}cur1 = n > 0 ? head1 : head2;cur2 = cur1 == head1 ? head2 : head1;n = Math.abs(n);while (n != 0) {n--;cur1 = cur1.next;}while (cur1 != cur2) {cur1 = cur1.next;cur2 = cur2.next;}return cur1;}public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {Node cur1 = null;Node cur2 = null;if (loop1 == loop2) {cur1 = head1;cur2 = head2;int n = 0;while (cur1 != loop1) {n++;cur1 = cur1.next;}while (cur2 != loop2) {n--;cur2 = cur2.next;}cur1 = n > 0 ? head1 : head2;cur2 = cur1 == head1 ? head2 : head1;n = Math.abs(n);while (n != 0) {n--;cur1 = cur1.next;}while (cur1 != cur2) {cur1 = cur1.next;cur2 = cur2.next;}return cur1;} else {cur1 = loop1.next;while (cur1 != loop1) {if (cur1 == loop2) {return loop1;}cur1 = cur1.next;}return null;}}public static void main(String[] args) {// 1->2->3->4->5->6->7->nullNode head1 = new Node(1);head1.next = new Node(2);head1.next.next = new Node(3);head1.next.next.next = new Node(4);head1.next.next.next.next = new Node(5);head1.next.next.next.next.next = new Node(6);head1.next.next.next.next.next.next = new Node(7);// 0->9->8->6->7->nullNode head2 = new Node(0);head2.next = new Node(9);head2.next.next = new Node(8);head2.next.next.next = head1.next.next.next.next.next; // 8->6System.out.println(getIntersectNode(head1, head2).value);// 1->2->3->4->5->6->7->4...head1 = new Node(1);head1.next = new Node(2);head1.next.next = new Node(3);head1.next.next.next = new Node(4);head1.next.next.next.next = new Node(5);head1.next.next.next.next.next = new Node(6);head1.next.next.next.next.next.next = new Node(7);head1.next.next.next.next.next.next = head1.next.next.next; // 7->4// 0->9->8->2...head2 = new Node(0);head2.next = new Node(9);head2.next.next = new Node(8);head2.next.next.next = head1.next; // 8->2System.out.println(getIntersectNode(head1, head2).value);// 0->9->8->6->4->5->6..head2 = new Node(0);head2.next = new Node(9);head2.next.next = new Node(8);head2.next.next.next = head1.next.next.next.next.next; // 8->6System.out.println(getIntersectNode(head1, head2).value);} }

輸出結(jié)果：

6 2 4

總結(jié)

以上是生活随笔為你收集整理的左神算法：两个单链表相交的一系列问题（链表是否有环 / 两无环链表是否相交 / 两有环链表是否相交）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。