【题目】 在本题中，单链表可能有环，也可能无环。给定两个
单链表的头节点 head1和head2，这两个链表可能相交，也可能
不相交。请实现一个函数， 如果两个链表相交，请返回相交的
第一个节点；如果不相交，返回null 即可。 要求：如果链表1
的长度为N，链表2的长度为M，时间复杂度请达到 O(N+M)，额外
空间复杂度请达到O(1)。
解题思路
把原问题分成两个子问题：1.判断链表是否有环 2.判断两个链表是否相交
子问题1的解法
准备2个指针：一个快指针F（一次走2步）和一个慢指针S（一次走一步）。如果快指针在走的过程中遇到null，直接返回无环。但如果有环，快指针和慢指针一定会在环上相遇。
一开始的链表结构是这样的，快指针F和慢指针S都指向头节点的位置
在这里插入图片描述
然后快指针到第3个节点，慢指针到第2个节点
在这里插入图片描述
下一步，快指针和慢指针的位置如下：
在这里插入图片描述
下一步：
在这里插入图片描述
下一步：
在这里插入图片描述
下一步：
在这里插入图片描述
这时，他俩相遇，相遇的时候，将快指针指向头节点， 然后快指着由一次走两步变成一次走一步。快指针和慢指针一定会在入环节点处相遇。（这是结论，我没法证明，但是代码证明它是对的）
在这里插入图片描述
代码实现：
public static Node getLoopNode(Node head) { //判断单链表是否有环，并返回第一个入环的节点
if (head == null || head.next == null || head.next.next == null) {
//如果不到3个节点，链表一定无环
return null;
}
Node n1 = head.next; // n1是慢指针
Node n2 = head.next.next; // n2是快指针
while (n1 != n2) { //快指针和慢指针相遇时，跳出循环
if (n2.next == null || n2.next.next == null) {
return null;
}
n2 = n2.next.next;
n1 = n1.next;
}
n2 = head; // 快指针指向头节点
while (n1 != n2) {
n1 = n1.next;
n2 = n2.next;
}
return n1;
}
子问题2的解法
两个链表相交与否有三种情况：
（1）两链表都无环（不相交）
（2）一个链表有环，一个链表无环（不相交）
（3）两个链表都有环，还分成三种子情况
-
如下图所示
在这里插入图片描述
两种思路
（1）先遍历一遍第一个链表，用一个HashMap,把他的所有节点放进去作为key，value不用管。然后遍历第二个链表，在遍历过程中查看每个节点是否在HashMap里，这样就可以找出两个链表第一个相交的节点。
（2）说起来比较复杂，直接上代码，里面都写好了注释。 判断两个无环链表是否相交：
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) { //计算出链表1的长度
n++;
cur1 = cur1.next;
}
while (cur2.next != null) { //计算出链表1和2的长度差值n
n--;
cur2 = cur2.next;
}
if (cur1 != cur2) {
return null;
}
//把长链表的头节点赋给cur1，短链表的头节点赋给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相遇的时候退出循环
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1; // 返回第一个入环的节点
}
- 判断两个有环链表是否相交：
public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) { //判断两个有环链表是否相交
Node cur1;
Node cur2;
if (loop1 == loop2) { //复用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) { //判断两个链表是否相交
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) { //判断两个链表是否相交
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) {
//如果不到3个节点，链表一定无环
return null;
}
Node n1 = head.next; // n1是慢指针
Node n2 = head.next.next; // n2是快指针
while (n1 != n2) { //快指针和慢指针相遇时，跳出循环
if (n2.next == null || n2.next.next == null) {
return null;
}
n2 = n2.next.next;
n1 = n1.next;
}
n2 = head; // 快指针指向头节点
while (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) { //计算出链表1的长度
n++;
cur1 = cur1.next;
}
while (cur2.next != null) { //计算出链表1和2的长度差值n
n--;
cur2 = cur2.next;
}
if (cur1 != cur2) {
return null;
}
//把长链表的头节点赋给cur1，短链表的头节点赋给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相遇的时候退出循环
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1; // 返回第一个入环的节点
}
public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) { //判断两个有环链表是否相交
Node cur1;
Node cur2;
if (loop1 == loop2) { //复用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);
}
}
