【題目】 在本題中，單鏈表可能有環(huán)喷市，也可能無環(huán)相种。給定兩個(gè)
單鏈表的頭節(jié)點(diǎn) head1和head2，這兩個(gè)鏈表可能相交品姓，也可能
不相交寝并。請實(shí)現(xiàn)一個(gè)函數(shù)， 如果兩個(gè)鏈表相交腹备，請返回相交的
第一個(gè)節(jié)點(diǎn)衬潦；如果不相交，返回null 即可植酥。 要求：如果鏈表1
的長度為N镀岛，鏈表2的長度為M，時(shí)間復(fù)雜度請達(dá)到 O(N+M)友驮，額外
空間復(fù)雜度請達(dá)到O(1)漂羊。
解題思路
把原問題分成兩個(gè)子問題：1.判斷鏈表是否有環(huán) 2.判斷兩個(gè)鏈表是否相交
子問題1的解法
準(zhǔn)備2個(gè)指針：一個(gè)快指針F（一次走2步）和一個(gè)慢指針S（一次走一步）。如果快指針在走的過程中遇到null卸留，直接返回?zé)o環(huán)走越。但如果有環(huán)，快指針和慢指針一定會在環(huán)上相遇耻瑟。
一開始的鏈表結(jié)構(gòu)是這樣的旨指，快指針F和慢指針S都指向頭節(jié)點(diǎn)的位置
在這里插入圖片描述
然后快指針到第3個(gè)節(jié)點(diǎn)，慢指針到第2個(gè)節(jié)點(diǎn)
在這里插入圖片描述
下一步喳整，快指針和慢指針的位置如下：
在這里插入圖片描述
下一步：
在這里插入圖片描述
下一步：
在這里插入圖片描述
下一步：
在這里插入圖片描述
這時(shí)谆构，他倆相遇，相遇的時(shí)候框都，將快指針指向頭節(jié)點(diǎn)搬素， 然后快指著由一次走兩步變成一次走一步∥罕＃快指針和慢指針一定會在入環(huán)節(jié)點(diǎn)處相遇蔗蹋。（這是結(jié)論，我沒法證明囱淋，但是代碼證明它是對的）
在這里插入圖片描述
代碼實(shí)現(xiàn)：
public static Node getLoopNode(Node head) { //判斷單鏈表是否有環(huán)猪杭，并返回第一個(gè)入環(huán)的節(jié)點(diǎn)
if (head == null || head.next == null || head.next.next == null) {
//如果不到3個(gè)節(jié)點(diǎn)，鏈表一定無環(huán)
return null;
}
Node n1 = head.next; // n1是慢指針
Node n2 = head.next.next; // n2是快指針
while (n1 != n2) { //快指針和慢指針相遇時(shí)妥衣，跳出循環(huán)
if (n2.next == null || n2.next.next == null) {
return null;
}
n2 = n2.next.next;
n1 = n1.next;
}
n2 = head; // 快指針指向頭節(jié)點(diǎn)
while (n1 != n2) {
n1 = n1.next;
n2 = n2.next;
}
return n1;
}
子問題2的解法
兩個(gè)鏈表相交與否有三種情況：
（1）兩鏈表都無環(huán)（不相交）
（2）一個(gè)鏈表有環(huán)皂吮，一個(gè)鏈表無環(huán)（不相交）
（3）兩個(gè)鏈表都有環(huán)戒傻，還分成三種子情況
-
如下圖所示
在這里插入圖片描述
兩種思路
（1）先遍歷一遍第一個(gè)鏈表，用一個(gè)HashMap,把他的所有節(jié)點(diǎn)放進(jìn)去作為key蜂筹，value不用管需纳。然后遍歷第二個(gè)鏈表，在遍歷過程中查看每個(gè)節(jié)點(diǎn)是否在HashMap里艺挪，這樣就可以找出兩個(gè)鏈表第一個(gè)相交的節(jié)點(diǎn)不翩。
（2）說起來比較復(fù)雜，直接上代碼麻裳，里面都寫好了注釋口蝠。 判斷兩個(gè)無環(huán)鏈表是否相交：
public static Node noLoop(Node head1, Node head2) { //判斷兩個(gè)無環(huán)鏈表是否相交
if (head1 == null || head2 == null) {
return null;
}
Node cur1 = head1;
Node cur2 = head2;
int n = 0;
while (cur1.next != null) { //計(jì)算出鏈表1的長度
n++;
cur1 = cur1.next;
}
while (cur2.next != null) { //計(jì)算出鏈表1和2的長度差值n
n--;
cur2 = cur2.next;
}
if (cur1 != cur2) {
return null;
}
//把長鏈表的頭節(jié)點(diǎn)賦給cur1，短鏈表的頭節(jié)點(diǎn)賦給cur2
cur1 = n > 0 ? head1 : head2;
cur2 = cur1 == head1 ? head2 : head1;
n = Math.abs(n);
while (n != 0) { //長鏈表的cur1先走n步津坑，然后與短鏈表的cur2一起走（相交）
n--;
cur1 = cur1.next;
}
while (cur1 != cur2) { //cur1和cur2相遇的時(shí)候退出循環(huán)
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1; // 返回第一個(gè)入環(huán)的節(jié)點(diǎn)
}
- 判斷兩個(gè)有環(huán)鏈表是否相交：
public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) { //判斷兩個(gè)有環(huán)鏈表是否相交
Node cur1;
Node cur2;
if (loop1 == loop2) { //復(fù)用noLoop方法
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 Node getIntersectNode(Node head1, Node head2) { //判斷兩個(gè)鏈表是否相交
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 class 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) { //判斷兩個(gè)鏈表是否相交
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) { //判斷單鏈表是否有環(huán)疆瑰，并返回第一個(gè)入環(huán)的節(jié)點(diǎn)
if (head == null || head.next == null || head.next.next == null) {
//如果不到3個(gè)節(jié)點(diǎn)眉反，鏈表一定無環(huán)
return null;
}
Node n1 = head.next; // n1是慢指針
Node n2 = head.next.next; // n2是快指針
while (n1 != n2) { //快指針和慢指針相遇時(shí)，跳出循環(huán)
if (n2.next == null || n2.next.next == null) {
return null;
}
n2 = n2.next.next;
n1 = n1.next;
}
n2 = head; // 快指針指向頭節(jié)點(diǎn)
while (n1 != n2) {
n1 = n1.next;
n2 = n2.next;
}
return n1;
}
public static Node noLoop(Node head1, Node head2) { //判斷兩個(gè)無環(huán)鏈表是否相交
if (head1 == null || head2 == null) {
return null;
}
Node cur1 = head1;
Node cur2 = head2;
int n = 0;
while (cur1.next != null) { //計(jì)算出鏈表1的長度
n++;
cur1 = cur1.next;
}
while (cur2.next != null) { //計(jì)算出鏈表1和2的長度差值n
n--;
cur2 = cur2.next;
}
if (cur1 != cur2) {
return null;
}
//把長鏈表的頭節(jié)點(diǎn)賦給cur1穆役，短鏈表的頭節(jié)點(diǎn)賦給cur2
cur1 = n > 0 ? head1 : head2;
cur2 = cur1 == head1 ? head2 : head1;
n = Math.abs(n);
while (n != 0) { //長鏈表的cur1先走n步寸五，然后與短鏈表的cur2一起走（相交）
n--;
cur1 = cur1.next;
}
while (cur1 != cur2) { //cur1和cur2相遇的時(shí)候退出循環(huán)
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1; // 返回第一個(gè)入環(huán)的節(jié)點(diǎn)
}
public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) { //判斷兩個(gè)有環(huán)鏈表是否相交
Node cur1;
Node cur2;
if (loop1 == loop2) { //復(fù)用noLoop方法
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(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->2
System.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->6
System.out.println(getIntersectNode(head1, head2).value);
}
}
