算法-面試題系列﹎﹎鏈表問題 ????鏈表相交與環(huán) ????
給定兩個(gè)可能有環(huán)也可能無環(huán)的單鏈表，頭節(jié)點(diǎn)head1和head2女揭。請實(shí)現(xiàn)一個(gè)函數(shù)窃植，如果兩個(gè)鏈表相交特石，請返回相交的第一個(gè)節(jié)點(diǎn)。
如果不相交卧秘，返回null
[要求]
如果兩個(gè)鏈表長度之和為N呢袱，時(shí)間復(fù)雜度請達(dá)到O(N)，額外空間復(fù)雜度請達(dá)到O(1)翅敌。
怎么樣判斷鏈表有環(huán)羞福？
1-使用HashSet
image-20210519195129198
2-使用快慢指針
結(jié)論一：快慢指針能夠判斷是否有環(huán) 也就是說能夠相遇就代表有環(huán)
-
結(jié)論二： 將快指針移至起點(diǎn)，與慢指針同速行進(jìn)蚯涮，兩者會(huì)在環(huán)入口處相遇治专；
image-20210519195802466
image-20210519201142207
// 找到鏈表第一個(gè)入環(huán)節(jié)點(diǎn)卖陵，如果無環(huán)，返回null
public static Node getLoopNode(Node head) {
if (head == null || head.next == null || head.next.next == null) {
return null;
}
// n1 慢 n2 快
Node slow = head.next; // n1 -> slow
Node fast = head.next.next; // n2 -> fast
while (slow != fast) {
if (fast.next == null || fast.next.next == null) {
return null;
}
fast = fast.next.next;
slow = slow.next;
}
// slow fast 相遇
fast = head; // n2 -> walk again from head
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
現(xiàn)在我們有了getLoopNode函數(shù)张峰，可以判斷鏈表是否有環(huán)的情況我們接下解決兩個(gè)兩個(gè)鏈表相交問題
情況一：兩個(gè)鏈表都是無歡鏈表
image-20210519213619626
兩個(gè)鏈表都是無環(huán)鏈表泪蔫，則end相同則判定相交。
image-20210519214318235
// 如果兩個(gè)鏈表都無環(huán)挟炬，返回第一個(gè)相交節(jié)點(diǎn)鸥滨，如果不想交，返回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;
while (cur1.next != null) {//計(jì)算長度
n++;
cur1 = cur1.next;
}
while (cur2.next != null) {//計(jì)算長度
n--;
cur2 = cur2.next;
}
if (cur1 != cur2) {//end 不相同谤祖，直接返回null 判定無相交節(jié)點(diǎn)婿滓，因?yàn)椴淮嬖谙嘟涣耍缓髢蓚€(gè)又分開的單鏈表結(jié)構(gòu)
return null;
}
// n : 鏈表1長度減去鏈表2長度的值
cur1 = n > 0 ? head1 : head2; // 誰長粥喜，誰的頭變成cur1
cur2 = cur1 == head1 ? head2 : head1; // 誰短凸主，誰的頭變成cur2
n = Math.abs(n);
while (n != 0) {//長鏈表先走N步
n--;
cur1 = cur1.next;
}
while (cur1 != cur2) {//兩個(gè)鏈表一起走。相同停止额湘，返回相交節(jié)點(diǎn)
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
}
情況二：兩個(gè)鏈表中卿吐，一個(gè)有環(huán)，一個(gè)無環(huán)
image-20210519215023659
這種情況是不可能相交的锋华，可以腦補(bǔ)各種情況嗡官，看看兩個(gè)單鏈表能夠相交否？
情況三：兩個(gè)鏈表都有環(huán)（3中形式）
- 有環(huán)不相交
image-20210519215258573
-
相交兩個(gè)鏈表同時(shí)入環(huán)
這種情況最好區(qū)分毯焕，如果Loop1==Loop2衍腥，說明同時(shí)入環(huán)
按兩個(gè)鏈表都是無歡鏈表，結(jié)尾為共同點(diǎn)的方式求解第一個(gè)相交點(diǎn)
image-20210519215501586
- 相交非同一個(gè)入環(huán)節(jié)點(diǎn)
求解方法纳猫，Loop1按環(huán)轉(zhuǎn)一圈婆咸，如果遇到了另一個(gè)節(jié)點(diǎn)Loop2，說明環(huán)里面有L2鏈表芜辕，相交
image-20210519215743710
// 兩個(gè)有環(huán)鏈表尚骄，返回第一個(gè)相交節(jié)點(diǎn)，如果不想交返回null
public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
Node cur1 = null;
Node cur2 = null;
if (loop1 == loop2) {//相交兩個(gè)鏈表同時(shí)入環(huán)
cur1 = head1;
cur2 = head2;
int n = 0;
while (cur1 != loop1) {//計(jì)算走到相交的長度
n++;
cur1 = cur1.next;
}
while (cur2 != loop2) {//計(jì)算走到相交的長度
n--;
cur2 = cur2.next;
}
cur1 = n > 0 ? head1 : head2;
cur2 = cur1 == head1 ? head2 : head1;
n = Math.abs(n);
while (n != 0) {//長鏈表先走n步
n--;
cur1 = cur1.next;
}
while (cur1 != cur2) {//兩個(gè)鏈表一起走侵续。相同停止倔丈，返回相交節(jié)點(diǎn)
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
} else {//相交節(jié)點(diǎn)不相同
cur1 = loop1.next;
while (cur1 != loop1) {//Loop1按環(huán)轉(zhuǎn)一圈，
if (cur1 == loop2) {//如果遇到了另一個(gè)節(jié)點(diǎn)Loop2,說明相交状蜗，直接返回
return loop1;
}
cur1 = cur1.next;
}
return null;//環(huán)轉(zhuǎn)了一圈乃沙，沒遇到，不相交
}
}
完整代碼
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) {
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;
}
// 找到鏈表第一個(gè)入環(huán)節(jié)點(diǎn)诗舰，如果無環(huán)警儒，返回null
public static Node getLoopNode(Node head) {
if (head == null || head.next == null || head.next.next == null) {
return null;
}
// n1 慢 n2 快
Node slow = head.next; // n1 -> slow
Node fast = head.next.next; // n2 -> fast
while (slow != fast) {
if (fast.next == null || fast.next.next == null) {
return null;
}
fast = fast.next.next;
slow = slow.next;
}
// slow fast 相遇
fast = head; // n2 -> walk again from head
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
// 如果兩個(gè)鏈表都無環(huán)，返回第一個(gè)相交節(jié)點(diǎn)，如果不想交蜀铲，返回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;
while (cur1.next != null) {
n++;
cur1 = cur1.next;
}
while (cur2.next != null) {
n--;
cur2 = cur2.next;
}
if (cur1 != cur2) {
return null;
}
// n : 鏈表1長度減去鏈表2長度的值
cur1 = n > 0 ? head1 : head2; // 誰長边琉，誰的頭變成cur1
cur2 = cur1 == head1 ? head2 : head1; // 誰短，誰的頭變成cur2
n = Math.abs(n);
while (n != 0) {
n--;
cur1 = cur1.next;
}
while (cur1 != cur2) {
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
}
// 兩個(gè)有環(huán)鏈表记劝，返回第一個(gè)相交節(jié)點(diǎn)变姨，如果不想交返回null
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;
}
}
}
