大家好，都吃晚饭了吗？我是Kaiqisan,是一个已经走出社恐的一般生徒,今天讲讲我至今碰到的最变态的链表题。
单链表两个单链表可能有环，可能无环，判断两个链表是否存在相交，如果有相交，返回其中一个交点
要求： 时间复杂度 O(m + n) 空间复杂度 O(1)（暗示不能使用hash表）
首先把所有的情况分出来，然后找出规律，分别解决（因为所有的情况都是可以罗列的）
首先要考虑到链表的特殊性，它只有一个next属性，所以每一个节点都只有一个箭头
先考虑两个链表分离的情况
第二种：一个有环一个无环
第三种：两个都是有环的
再考虑两个链表有相交的情况
第四种：两个都是无环的
判断完所有的情况之后开始解题
我们可以先从两个头结点开始，从头到尾遍历，
如果最终走到了结尾，(出现了tempNode == null),就是情况4和情况4，这个时候可以再让两个链表从头走到尾，统计步数，a, b （a > b）,然后再让长链表先走 (a - b)步，接下来短链表开始走，每走一步判断地址值是否相等，如果有相等的，就存在相交点，如果走到了终点都没有的话就没有相交点。
当两个链表都没有走到结尾的时候会返回一个loop节点（就是循环开始的节点）
从头结点开始使用快慢指针，找到第一个相交的点（因为最后它们都会在一个环里面，所以这就变成了一个追及问题）。然后慢指针记录交点，快指针回到头结点，开始和慢指针一个速度前进，如果两个指针相遇，这个相遇的节点必然是交点，如果有一个指针走向终点，就没有loop节点。
现在我们从追记问题的总距离这里来解释为什么后面说 两个指针相遇，这个相遇的节点必然是交点
我们看出快指针比慢指针多走一个环，现在我们假设快指针的速度为2个节点 / 秒，慢指针的速度为1个节点 / 秒，求两个节点的相交地点。
现在我们假设链表长 len，环周长为 a
慢节点走过n，那么快节点走过2n
有
n + a = 2n
a = n
所以慢节点走过一个环的周长的距离a，到达loop节点处还有 len - a距离，
然后让快节点回到起点和慢节点一个速度开始往下走，快节点也是需要走 len - a距离才可以到loop节点处
所以
快慢节点最终必然会在loop节点处相交
我们先分别让两个指针a, b分别从head1 head2开始遍历，得分别出两个距离 m 和 n，比较两个距离大小
现在假设m > n ，
接下来我们让两个指针分别回到各自的头结点，先让a指针先走 m - n 步，然后b指针才开始起步，直到两个指针指向同一个地址（交汇了），第一个交汇的指针就是交点
现在咱来具体分析下步骤
假设两个指针在第一次遍历走过的共同的路程为
x(图中绿色路径)，以下简称后半段，也简称他们路径交汇之前的路径为前半段。
那么在两个节点走前半段的路径分别为n-xm-x
那么
两个前半段路径之差为m - n
所以在第二次遍历的时候先让b指针先走m - n长度，然后再a, b指针一起走，只需要走n个距离就会在交点交汇，
这个交汇点就是两个链表的交点
PS:情况5的第二种也可以使用上面的思路来解决
这个只要返回其中一个交点就可以了
为了排除情况3
需要判断loop1节点是否可以走到loop2节点，如果从loop1节点开始转圈遍历的时候，在回到loop1之前没有碰到loop2节点,那就是情况3，
反之
就是情况5的第一种
static LinkList doJudge(LinkList head1, LinkList head2) {
if (head1 == null || head2 == null) {
return null;
}
LinkList loop1 = getLoopNode(head1);
LinkList loop2 = getLoopNode(head2);
// 俩都无环的情况，判断是相交还是不相交，如果相交返回相交节点，不相交返回null
if (loop1 == null && loop2 == null) {
return noLoop(head1, head2);
}
// 一个有环一个无环的情况，且必然相交，找交点
if (loop1 != null && loop2 != null) {
return bothLoop(head1, head2, loop1, loop2);
}
// 一个有环一个无环不相交的情况必然无交点，所以返回null
return null;
}
static LinkList getLoopNode(LinkList head) {
if (head == null || head.next == null || head.next.next == null) {
return null;
}
// 快慢指针打大发好
LinkList slow = head.next;
LinkList fast = head.next.next;
// 考虑到结点很短，无法组成环（两个以下的节点）
while (fast != slow) {
if (fast.next == null || fast.next.next == null) {
return null;
}
fast = fast.next.next;
slow = slow.next;
}
fast = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
static LinkList noLoop(LinkList head1, LinkList head2) {
int n = 0;
LinkList temp1 = head1;
LinkList temp2 = head2;
// 判断从头结点开始走向尾节点要的步数
// 然后找出差值
// 不要走到头，到最后一个节点停下以便判断节点是否相交
while (temp1.next != null) {
n++;
temp1 = temp1.next;
}
while (temp2.next != null) {
n--;
temp2 = temp2.next;
}
if (temp1 != temp2) {
return null;
}
temp1 = n > 0 ? head1 : head2;
temp2 = temp1 == head1 ? head2 : head1;
n = Math.abs(n);
while (n != 0) {
n--;
temp1 = temp1.next;
}
while (temp1 != temp2) {
temp1 = temp1.next;
temp2 = temp2.next;
}
return temp1;
}
static LinkList bothLoop(LinkList head1, LinkList head2, LinkList loop1, LinkList loop2) {
LinkList temp1 = null;
LinkList temp2 = null;
// 和情况3一样，只不过最后的终点只是到loop结点
if (loop1 == loop2) {
temp1 = head1;
temp2 = head2;
int n = 0;
while (temp1 != loop1) {
n++;
temp1 = temp1.next;
}
while (temp2 != loop1) {
n--;
temp2 = temp2.next;
}
temp1 = n > 0 ? head1 : head2;
temp2 = temp1 == head1 ? head2 : head1;
n = Math.abs(n);
while (n != 0) {
n--;
temp1 = temp1.next;
}
while (temp1 != temp2) {
temp1 = temp1.next;
temp2 = temp2.next;
}
return temp1;
} else {
temp1 = loop1.next;
// 转一圈
while (temp1 != loop1) {
// 如果遇到loop2就返回
if (temp1 == loop2) {
return loop1;
}
temp1 = temp1.next;
}
return null;
}
}
还是挺复杂的，会了这道题之后几乎就可以斩杀大部分的链表题目了！（反正以后的链表题我都用java来耍了）
代码很多，但是如果您很熟悉链表的话，就把上面的代码分模块来看，拆分之后就会变得容易很多。