算法-面试题系列﹎﹎链表问题 🏅🏅链表相交与环 🏅🏅
给定两个可能有环也可能无环的单链表，头节点head1和head2。请实现一个函数，如果两个链表相交，请返回相交的第一个节点。
如果不相交，返回null
[要求]
如果两个链表长度之和为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1)。
怎么样判断链表有环？
1-使用HashSet
image-20210519195129198
2-使用快慢指针
结论一：快慢指针能够判断是否有环 也就是说能够相遇就代表有环
-
结论二： 将快指针移至起点，与慢指针同速行进，两者会在环入口处相遇；
image-20210519195802466
image-20210519201142207
// 找到链表第一个入环节点，如果无环，返回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;
}
现在我们有了getLoopNode函数，可以判断链表是否有环的情况我们接下解决两个两个链表相交问题
情况一：两个链表都是无欢链表
image-20210519213619626
两个链表都是无环链表，则end相同则判定相交。
image-20210519214318235
// 如果两个链表都无环，返回第一个相交节点，如果不想交，返回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) {//end 不相同，直接返回null 判定无相交节点，因为不存在相交了，然后两个又分开的单链表结构
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) {//两个链表一起走。相同停止，返回相交节点
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
}
情况二：两个链表中，一个有环，一个无环
image-20210519215023659
这种情况是不可能相交的，可以脑补各种情况，看看两个单链表能够相交否？
情况三：两个链表都有环（3中形式）
- 有环不相交
image-20210519215258573
-
相交两个链表同时入环
这种情况最好区分，如果Loop1==Loop2，说明同时入环
按两个链表都是无欢链表，结尾为共同点的方式求解第一个相交点
image-20210519215501586
- 相交非同一个入环节点
求解方法，Loop1按环转一圈，如果遇到了另一个节点Loop2，说明环里面有L2链表，相交
image-20210519215743710
// 两个有环链表，返回第一个相交节点，如果不想交返回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步
n--;
cur1 = cur1.next;
}
while (cur1 != cur2) {//两个链表一起走。相同停止，返回相交节点
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
} else {//相交节点不相同
cur1 = loop1.next;
while (cur1 != loop1) {//Loop1按环转一圈，
if (cur1 == loop2) {//如果遇到了另一个节点Loop2,说明相交，直接返回
return loop1;
}
cur1 = cur1.next;
}
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) {
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;
}
// 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;
}
// 如果两个链表都无环，返回第一个相交节点，如果不想交，返回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;
}
// 两个有环链表，返回第一个相交节点，如果不想交返回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;
}
}
}
