寻找链表相交结点问题
作者：Grey
原文地址：
题目描述#
给定两个可能有环也可能无环的单链表，头节点head1和head2。请实现一个函数，如果两个链表相交，请返回相交的 第一个节点。如果不相交，返回 null。
要求：如果两个链表长度之和为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1)。
类似问题#
本题主要的难点是要分析所有可能的情况，因为题目中提到「可能有环也可能无环」。
主要思路#
先看大的情况，有如下三种情况
第一种情况：两个链表均无环；
第二种情况：两个链表均有环；
第三种情况：一个有环，一个无环。
首先，第三种情况下，两个链表一定不相交。针对第一种情况，就是寻找链表的入环节点和相交节点问题中提到LeetCode 160. Intersection of Two Linked Lists，现在只分析第二种情况。
由于两个链表都有环，两个链表如果相交，一定只有如下三种情况
情况1：两个链表独立不相交
情况2：两个链表的入环结点是同一个
情况3：两个链表的入环结点不是同一个，此时任意一个链表的入环结点都是相交结点。
先从最简单的情况1和情况3进行分析，情况一发生的条件是：两个链表的入环结点（loop1，loop2）不是同一个，判断条件很简单，就是从任意一个链表的入环结点开始遍历一圈，如果都没有遇到另外一个链表的入环结点, 两个链表不相交，属于情况1；
如果从任意一个链表的入环结点开始遍历一圈，遇到了另外一个链表的入环结点，则说明两个链表相交，属于情况3，且任意一个链表的入环结点都是相交结点。
最后分析情况2，两个链表的入环结点如果是同一个，可以记录两个链表的差值，然后让短链表先走差值步以后，长短链表同时开始走，相遇的结点就是第一个相交结点。
完整代码见：
public class Code_FindFirstIntersectNode {
public static class List {
public int val;
public List next;
public List(int v) {
val = v;
}
}
public static List getIntersectNode(List head1, List head2) {
if (head1 == null || head2 == null) {
return null;
}
// 两个均无环
List loop1 = getLoopNode(head1);
List 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 List getLoopNode(List head) {
if (head == null || head.next == null || head.next.next == null) {
return null;
}
// 慢指针 在第一个节点位置
List slow = head.next;
// 快指针，在第二个节点的位置
List fast = head.next.next;
while (slow != fast) {
if (fast.next == null || fast.next.next == null) {
return null;
}
// 快指针每次走两步
fast = fast.next.next;
// 慢指针每次走一步
slow = slow.next;
}
// 两个指针遇上了，说明有环
// 让快指针回到头部， 慢指针停在原地
fast = head;
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
// 快指针每次走一步，慢指针每次走一步，遇上后，就是入环节点处
return slow;
}
// 如果两个链表都无环，返回第一个相交节点，如果不想交，返回null
public static List noLoop(List head1, List head2) {
if (head1 == null || head1 == null) {
return null;
}
// 判断两个链表的长度
int n = 0;
List t1 = head1;
List t2 = head2;
while (t1.next != null) {
n++;
t1 = t1.next;
}
while (t2.next != null) {
n--;
t2 = t2.next;
}
// 两个链表的末节点不相等
if (t2 != t1) {
return null;
}
// 记录长的链表头节点
List longer = n > 0 ? head1 : head2;
// 记录短的链表头节点
List shorter = longer == head1 ? head2 : head1;
// 先让长链表走一段距离（这段的长度就是长链表和短链表的长度差）
int gap = Math.abs(n);
while (gap != 0) {
gap--;
longer = longer.next;
}
// 然后长链表和短链表同时开始走，直到相等的节点即为交点
while (longer != shorter) {
longer = longer.next;
shorter = shorter.next;
}
return shorter;
}
// 两个有环链表，返回第一个相交节点，如果不想交返回null
public static List bothLoop(List head1, List loop1, List head2, List loop2) {
// 只有两种情况
if (loop1 == loop2) {
// 1. 未入环就相交
// 这种情况下，两个链表的入环节点是一样
int n = 0;
List t1 = head1;
List t2 = head2;
while (t1 != loop1) {
n++;
t1 = t1.next;
}
while (t2 != loop2) {
n--;
t2 = t2.next;
}
List longer = n > 0 ? head1 : head2;
List shorter = longer == head1 ? head2 : head1;
n = Math.abs(n);
while (n != 0) {
n--;
longer = longer.next;
}
while (longer != shorter) {
longer = longer.next;
shorter = shorter.next;
}
return shorter;
} else {
// 2. 共用环，不在入环处相交，随便一个链表的入环点就是交点
// loop1 != loop2
// 从loop1开始，转一圈回到loop1
// 如果都没有遇到loop2，则不相交
// 如果遇到了loop1，则交点为loop1或者loop2都可以
List t1 = loop1.next;
while (t1 != loop1) {
if (t1 == loop2) {
return loop1;
}
t1 = t1.next;
}
return null;
}
}
}