前言：此题是链表里面的两大噩梦之一，另一个难题就是约瑟夫环。但是作者在自己理解的基础上，尽可能写明白，让读者能够理解~~~///(v)\\\~~~。
题目：给定两个可能有环也可能无环的单链表，头节点head1和head2。请实现一个函数，如果两个链表相交，请返回相交的第一个节点。如果不相交，返回null。【要求】：如果两个链表长度之和为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1)。
分析题目
情况分为以下几种：
- 两个链表都无环
- 一个有环一个无环
- 两个都有环
那么，首先我们要明确一点：两个链表，一个有环一个无环，那么两个链表必定不相交，因为只有一条next指针！！！，请驱除自己野马般的想法。所以，第二种情况很好处理，按题目要求直接返回null就好了。
那么我们先来看，如何找到链表的第一个入环结点，如果无环，返回null。这样我们才好讨论第一种情况和第三种情况。
所以现在我们要解决的问题是：找到链表第一个入环节点，如果无环，返回null。这是我们的第一个函数getLoopNode()，找到链表第一个入环结点。那么，函数具体如何实现？
方法有两种：
- 方法一：用HashSet。只需要用到HashSet，用HashSet记录沿途所有结点。一开始HashSet里面是空的，然后开始查链表的结点有没有在HashSet里，没有的话，在HashSet里记录该结点，有的话，就是第一个入环结点，如果没有环，一定会走到null。注意：沿途遍历链表一定要先查再放！！！查的第一个在HashSet里的就是第一个入环结点
- 方法二：推荐使用这种，因为更省空间！ 使用快慢指针，慢指针一次走一步，快指针一次走两步。一开始，让慢指针来到第二个结点，快指针来到第三个结点。为什么要都先走一步？因为循环结束条件是快慢指针走到同一个结点。如果链表有环的话，快慢指针一定会走到同一个结点。如果快指针提前走到null，必定无环。接下来，快指针回到头结点，满指针停到原地，快慢指针同时走，每次都只走一步，再一次重合的结点必定是入环的第一个结点
Node slow = head.next; Node fast = head.next.next;
所以通过函数getLoopNode()，我们知道了两个链表是否有环。
那么我们现在只需要考虑两个链表都有环和两个链表都无环的情况，都有环的情况比较复杂，所以先考虑都无环的情况
两个链表都无环的情况下，如何找到第一个相交结点。也就得到了第二个函数noLoop()，两个无环链表，返回第一个相交节点，如果不相交，返回null，这个函数具体如何实现呢？首先我们知道，两个无环链表，如果不相交，则是各自独立的两条线。如果相交，则最后一定是公共部分，因为只有一条next指针！！！ 同样，两个无环链表找第一个相交结点也有两种方法：
- 方法一：用哈希表，将其中一条链表放入HashSet里，然后遍历另一条链表时查当前结点是否在HashSet里。
- 方法二：推荐使用这种，因为更省空间！ 彻底不用哈希表，找到两条链表的最后一个结点（所谓最后一个结点是指：当前结点不是空，再往下走就是空），分别记为end1和end2。如果end1!=end2(内存地址不一样)，说明不相交。因为如果相交，必定共用同一部分，那么内存地址必定一样。如果end1==end2，长链表先走，走的长度为为：长链表的长度-短链表的长度。然后短链表再从头结点开始走，则一定会在第一个相交结点处相遇。
由此，只剩下第三种情况，两个链表都有环没有讨论了。第三个函数bothLoop()，两个有环链表，返回第一个相交节点，如果不想相交，返回null。而第三种情况又有三种情况：
（首先要明确一点：两个有环链表相交一定共用同一个环，所以关键在于入环结点是不是同一个）
loop1和loop2代表两个链表第一个入环结点
- 1》两个有环链表各自独立(loop1!=loop2)。
- 2》两个有环链表入环结点是同一个点(loop1loop2)。如果两个链表的第一个入环结点的内存地址一样(loop1loop2)，则满足此种情况。因为loop1和loop2代表两个链表第一个入环结点， 且都不为null，且内存地址也一样。那么，此种情况下如何找第一个相交的结点呢？此时，跟环已经没有关系。原来两个无环链表相交时，假设的是null位置是终点位置；那么现在，假设的便是第一个入环结点是终止位置
- 3》两个有环链表入环结点不是同一个(loop1!=loop2)
如何区分1》和3》，让loop1往下走，如果转一圈回到自己都没有遇到过loop2就是情况1》；让loop1往下走，如果回到自己前遇到了loop2就是情况3》
不知道你有没有被绕晕呢，如果有就多看几遍啦。
最后总结一下，经过上面的分析后，主函数getFirstIntersectNode()的实现就很简单了。先调用第一个函数getLoopNode()，找到链表的第一个入环结点，如果两个链表都无环，调用第二个函数noLoop()，如果两个链表都有环，调用第三个函数bothLoop()。如果一个有环，一个无环，两个链表必定不会相交，因为只有一条next指针！
最后，这个题其实是三个面试题的合集：
- 给你一个链表，返回第一个入环的节点
- 两个无环链表相交，返回第一个相交节点
- 两个有环链表相交，返回第一个相交节点
最后贴上代码：
package com.harrison.class06; public class Code05_FindFirstIntersectNode { public static class Node { public int value; public Node next; public Node(int v) { value = v; } } public static Node getFirstIntersectNode(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; } Node slow = head.next; Node fast = head.next.next; while (slow != fast) {// 如果链表有环的话，快慢指针一定会走到同一个结点 // 快指针提前走到null，必定无环 if (fast.next == null || fast.next.next == null) { return null; } slow = slow.next; fast = fast.next.next; } fast = 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;// 记录两条链表长度的差值 // n>0 cur1长 n==0 一样长 n<0 cur2长 while (cur1.next != null) { n++; cur1 = cur1.next; } while (cur2.next != null) { n--; cur2 = cur2.next; } // 结束两个while循环后，两个链表的当前节点分别来到了end1和end2 // 如果end1!=end2，说明没有共用一块内存地址，两个链表必不相交 if (cur1 != cur2) { return null; } // 人为规定：cur1为长链表，cur2为短链表 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; } // 两个有环链表，返回第一个相交节点，如果不想相交，返回null // head1和head2 分别代表两个链表第一个入环结点 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; } } 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(getFirstIntersectNode(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(getFirstIntersectNode(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(getFirstIntersectNode(head1, head2).value); } }
如果你看到这来了，不妨给个三连吧哈哈哈。
