【题目】 两个单向链表相交的一系列问题
在本题中，单链表可能有环，也可能无环。给定两个单链表的头节点 head1和head2，这两个链表可能相交，也可能不相交。请实现一个函数， 如果两个链表相交，请返回相交的第一个节点；如果不相交，返回null 即可。
【要求】
如果链表1的长度为N，链表2的长度为M，时间复杂度请达到 O(N+M)，额外空间复杂度请达到O(1)。
【分析】
本题目可以拆分为：
问题1.如何判断单链表有环还是无环，有环返回第一个入环节点，无环返回null
第一种方法
可以利用哈希表（hashSet）：遍历每一个节点，想要把每个结点都存放到哈希表中；但是哈希表中已经存过的节点就存不进去了（第一个不能存入哈希表的节点就是第一个入环的节点）。
注：需要一个哈希表，空间复杂度O(n)不满足。
第二种方法
设定两个指针：一个快指针（走两步），一个慢指针（走一步）；当快指针和慢指针相遇的时候，快指针回到头结点的位置，和慢指针一起以一步的步幅走，相遇的节点就是第一个入环节点。
【代码实现】
//1.定义结点的结构
public static class Node{
int value;
Node next;
public Node(int data) {
this.value=data;
}
}
//2.判断有环还是无环的方法，返回第一个入环节点
public static Node getLoopNode(Node head) {
//2.1小于三个结点肯定构不成环
if(head==null||head.next==null||head.next.next==null) {
return null;
}
//2.2快指针和慢指针移动找相遇的节点
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;
}
//2.3两个节点相遇，快指针回到头，和慢指针一起以一步的步幅走，相遇的就是第一个的入环节点
n2=head;
while(n1!=n2) {
n1=n1.next;
n2=n2.next;
}
return n1;
}
问题2.两个无环链表怎么找到第一个相交的节点
结构示意图
第一种方法
利用哈希表：
遍历第一个链表，把所有的节点都存入到哈希表中（因为是无环链表，所以一定可以存进去）（哈希表中存放的节点的内存地址，和节点的值没有关系）；遍历第二个链表的节点，每遍历一个查看哈希表中是否已经有了这个节点，哈希表中第一个存不进去的节点就是第一个相交节点。
哈希表空间复杂度是O(n)，不满足题目要求。
第二种方法
1.先确定两个链表的长度差
2.两个链表在移动的过程中，如果相交了（根据链表的特殊性，只有一个next指针，只能连接一个下一个结点，所以第一个公共结点之后，只知道链表的结尾都是相同的）（变量中存放的是内存地址，和数据无关），那么末尾的内存地址一定是相同的
3.如果最后的相等，那么说明是有相交的节点的，但是不一定是最后一个。
4.让长的节点从头开始，先走距离差个距离；短的从头开始走，相等的就是他们相交的节点
【代码实现】
public static Node noLoop(Node head1,Node head2) {
//1.如果有一个为空链表，那么一定没有相交结点
if(head1==null||head2==null) {
return null;
}
//2.两个链表中的节点分别往下走，走到末尾确定他们的长度差
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;
}
//3.如果走到最后了，也没有内存地址相同的节点，那么就说明没有相交的节点
if (cur1!=cur2) {
return null;
}
//4.确定那个链表是长链表cur1，那个是短链表cur2
//如果n>0,说明1比2长，那么确定要往回走的链表是长的那个cur1；
cur1=n>0?head1:head2;
//如果长的链表是1，那么cur2表示的就是短的链表，否则的话相反
cur2=cur1==head1?head2:head1;
//5.确定距离差
n=Math.abs(n);
//6.长的链表从头开始先移动距离差个距离
while(n!=0) {
n--;
cur1=cur1.next;
}
//7.如果cur1不等于cur2 说明长链表中前n个结点是不相交的，两个都一起移动，找到相等的点就是相交的点
while(cur1!=cur2) {
cur1=cur1.next;
cur2=cur2.next;
}
return cur1;
}
问题3 一个有环链表和一个无环列表怎么找到第一个相交的节点
可以得出结论就是这两个链表不可能相交。
因为链表的特性决定了如果两个链表相交的话，它们之后会一直相交下去，（相当于两个链表是从属关系，认为是一个链表了）。
无环的和有环的链表不能有公共的结点。
问题4 两个有环链表怎么找到第一个相交点
第一种情况：两个环没有任何关系，各自有各自的环
第二种情况：两个链表相交之后共享同一个环（同一个入环节点就是这种结构）
第三种情况：两个链表入环节点不一样个，但是同样共享一个环（不同的入环节点）
【思路】
1.调用问题1中找到入环节点的方法，找到两个链表的入环点loop1和loop2；
2.用loop1和loop2表示每一个链表的入环点，如果相等表示入环点相等，那么就是第二种情况；
找到相交点的步骤是：不考虑下面的环，然后是两个无环链表找相交点的方法
3.loop1和loop2不相等，说明是第一种情况和第三种情况。
让loop1不断往下走，如果走回自己了，还没碰到loop2，说明不是一个环，那么就是第一种情况，没有相交点；如果在走回自己的过程中，碰到了loop2，那么说明是一个环，是第三种情况，返回的是loop1还是loop2那个是相交点都对（只是针对不同的链表来说的）
【代码实现】
public static Node bothLoop(Node head1,Node head2,Node loop1,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) {
cur1=cur1.next;
n--;
}
if(cur1!=cur2) {
cur1=cur1.next;
cur2=cur2.next;
}
return cur1;
}else {
//loop1!=loop2是1或者3结构，让loop1移动
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, head2, loop1, loop2);
}
return null;
}