前言：此題是鏈表里面的兩大噩夢之一，另一個難題就是約瑟夫環，但是作者在自己理解的基礎上，盡可能寫明白，讓讀者能夠理解~~~///(v)\\\~~~，
題目：給定兩個可能有環也可能無環的單鏈表，頭節點head1和head2，請實作一個函式，如果兩個鏈表相交，請回傳相交的第一個節點，如果不相交，回傳null，【要求】：如果兩個鏈表長度之和為N，時間復雜度請達到O(N)，額外空間復雜度請達到O(1)，
分析題目
情況分為以下幾種：
- 兩個鏈表都無環
- 一個有環一個無環
- 兩個都有環
那么，首先我們要明確一點：兩個鏈表，一個有環一個無環，那么兩個鏈表必定不相交，因為只有一條next指標！！！，請驅除自己野馬般的想法，所以，第二種情況很好處理，按題目要求直接回傳null就好了，
那么我們先來看，如何找到鏈表的第一個入環結點，如果無環，回傳null，這樣我們才好討論第一種情況和第三種情況，
所以現在我們要解決的問題是：找到鏈表第一個入環節點，如果無環，回傳null，這是我們的第一個函式getLoopNode()，找到鏈表第一個入環結點，那么，函式具體如何實作？
方法有兩種：
- 方法一：用HashSet，只需要用到HashSet，用HashSet記錄沿途所有結點，一開始HashSet里面是空的，然后開始查鏈表的結點有沒有在HashSet里，沒有的話，在HashSet里記錄該結點，有的話，就是第一個入環結點，如果沒有環，一定會走到null，注意：沿途遍歷鏈表一定要先查再放！！！查的第一個在HashSet里的就是第一個入環結點
- 方法二：推薦使用這種，因為更省空間！ 使用快慢指標，慢指標一次走一步，快指標一次走兩步，一開始，讓慢指標來到第二個結點，快指標來到第三個結點，為什么要都先走一步？因為回圈結束條件是快慢指標走到同一個結點，如果鏈表有環的話，快慢指標一定會走到同一個結點，如果快指標提前走到null，必定無環，接下來，快指標回到頭結點，滿指標停到原地，快慢指標同時走，每次都只走一步，再一次重合的結點必定是入環的第一個結點
Node slow = head.next;
Node fast = head.next.next;
所以通過函式getLoopNode()，我們知道了兩個鏈表是否有環，
那么我們現在只需要考慮兩個鏈表都有環和兩個鏈表都無環的情況，都有環的情況比較復雜，所以先考慮都無環的情況
兩個鏈表都無環的情況下，如何找到第一個相交結點，也就得到了第二個函式noLoop()，兩個無環鏈表，回傳第一個相交節點，如果不相交，回傳null，這個函式具體如何實作呢？首先我們知道，兩個無環鏈表，如果不相交，則是各自獨立的兩條線，如果相交，則最后一定是公共部分，因為只有一條next指標！！！ 同樣，兩個無環鏈表找第一個相交結點也有兩種方法：
- 方法一：用哈希表，將其中一條鏈表放入HashSet里，然后遍歷另一條鏈表時查當前結點是否在HashSet里，
- 方法二：推薦使用這種，因為更省空間！ 徹底不用哈希表，找到兩條鏈表的最后一個結點（所謂最后一個結點是指：當前結點不是空，再往下走就是空），分別記為end1和end2，如果end1!=end2(記憶體地址不一樣)，說明不相交，因為如果相交，必定共用同一部分，那么記憶體地址必定一樣，如果end1==end2，長鏈表先走，走的長度為為：長鏈表的長度-短鏈表的長度，然后短鏈表再從頭結點開始走，則一定會在第一個相交結點處相遇，
由此，只剩下第三種情況，兩個鏈表都有環沒有討論了，第三個函式bothLoop()，兩個有環鏈表，回傳第一個相交節點，如果不想相交，回傳null，而第三種情況又有三種情況：
（首先要明確一點：兩個有環鏈表相交一定共用同一個環，所以關鍵在于入環結點是不是同一個）
loop1和loop2代表兩個鏈表第一個入環結點
- 1》兩個有環鏈表各自獨立(loop1!=loop2)，
- 2》兩個有環鏈表入環結點是同一個點(loop1loop2)，如果兩個鏈表的第一個入環結點的記憶體地址一樣(loop1loop2)，則滿足此種情況，因為loop1和loop2代表兩個鏈表第一個入環結點， 且都不為null，且記憶體地址也一樣，那么，此種情況下如何找第一個相交的結點呢？此時，跟環已經沒有關系，原來兩個無環鏈表相交時，假設的是null位置是終點位置；那么現在，假設的便是第一個入環結點是終止位置
- 3》兩個有環鏈表入環結點不是同一個(loop1!=loop2)
如何區分1》和3》，讓loop1往下走，如果轉一圈回到自己都沒有遇到過loop2就是情況1》；讓loop1往下走，如果回到自己前遇到了loop2就是情況3》
不知道你有沒有被繞暈呢，如果有就多看幾遍啦，
最后總結一下，經過上面的分析后，主函式getFirstIntersectNode()的實作就很簡單了，先呼叫第一個函式getLoopNode()，找到鏈表的第一個入環結點，如果兩個鏈表都無環，呼叫第二個函式noLoop()，如果兩個鏈表都有環，呼叫第三個函式bothLoop()，如果一個有環，一個無環，兩個鏈表必定不會相交，因為只有一條next指標！
最后，這個題其實是三個面試題的合集：
- 給你一個鏈表，回傳第一個入環的節點
- 兩個無環鏈表相交，回傳第一個相交節點
- 兩個有環鏈表相交，回傳第一個相交節點
最后貼上代碼：
package com.harrison.class06;
public class Code05_FindFirstIntersectNode {
public static class Node {
public int value;
public Node next;
public Node(int v) {
value = v;
}
}
public static Node getFirstIntersectNode(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;
}
// 找到鏈表第一個入環節點，如果無環，回傳null
public static Node getLoopNode(Node head) {
// 鏈表為空 或者只有一個結點 或者兩個，必然無環
if (head == null || head.next == null || head.next.next == null) {
return null;
}
Node slow = head.next;
Node fast = head.next.next;
while (slow != fast) {// 如果鏈表有環的話，快慢指標一定會走到同一個結點
// 快指標提前走到null，必定無環
if (fast.next == null || fast.next.next == null) {
return null;
}
slow = slow.next;
fast = fast.next.next;
}
fast = head;// 快指標來到頭結點 慢指標停在原地
// 再一次重合的結點必定是入環的第一個結點
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
// 兩個無環鏈表，回傳第一個相交節點，如果不相交，回傳null
public static Node noLoop(Node head1, Node head2) {
if (head1 == null || head2 == null) {
return null;
}
Node cur1 = head1;
Node cur2 = head2;
int n = 0;// 記錄兩條鏈表長度的差值
// n>0 cur1長 n==0 一樣長 n<0 cur2長
while (cur1.next != null) {
n++;
cur1 = cur1.next;
}
while (cur2.next != null) {
n--;
cur2 = cur2.next;
}
// 結束兩個while回圈后，兩個鏈表的當前節點分別來到了end1和end2
// 如果end1!=end2，說明沒有共用一塊記憶體地址，兩個鏈表必不相交
if (cur1 != cur2) {
return null;
}
// 人為規定：cur1為長鏈表，cur2為短鏈表
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;
}
// 兩個有環鏈表，回傳第一個相交節點，如果不想相交，回傳null
// head1和head2 分別代表兩個鏈表第一個入環結點
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->null
Node 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->null
Node 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->6
System.out.println(getFirstIntersectNode(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->2
System.out.println(getFirstIntersectNode(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->6
System.out.println(getFirstIntersectNode(head1, head2).value);
}
}
如果你看到這來了，不妨給個三連吧哈哈哈，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/377058.html
標籤：java