在上一篇文档中，通过java实现了单链表反转的问题，之后发现一个更有意思的问题就是如何判断两个链表是否相交？如果相交，则需要得到交点。
对于这个问题，需要分别考虑链表上是否存在环的情况。
//链表节点
public class DataNode {
private int data;
private DataNode next;
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public DataNode getNext() {
return next;
}
public void setNext(DataNode next) {
this.next = next;
}
public DataNode(int data) {
this.data = data;
}
}
1.两个链表都不存在环
对于这种情况，如果两个链表相交，又都不存在环，那么不难想象这两个链表共同构成了一个Y型。因此，只要分别遍历这两个链表，找到尾端节点，判断尾端节点是否相同即可确认是否相交。
如果要求这种情况的交点，由于相交部分全部都相同，因此，只需要先得到两个链表的差，用两个指针分别指向这两个链表P1,P2假定P1与P2相差为N，那么将P1移动N个节点后，P1与P2同时出发，第一个相等的节点即为交点。
/**
* 无环情况下，判断两个链表是否相交，只需要遍历链表，判断尾节点是否相等即可。
* @param h1
* @param h2
* @return
*/
public static boolean isJoinNoLoop(DataNode h1,DataNode h2) {
DataNode p1 = h1;
DataNode p2 = h2;
while(null != p1.getNext())
p1 = p1.getNext();
while(null != p2.getNext())
p2 = p2.getNext();
return p1 == p2;
}
/**
* 无环情况下找到第一个相交点
* 方法： 算出两个链表的长度差为x,长链表先移动x步，之后两链表同时移动，直到相遇的第一个交点。
* @param h1
* @param h2
* @return
*/
public static DataNode getFirstJoinNode(DataNode h1,DataNode h2) {
int length1 = 0;
int length2 = 0;
while(null != h1.getNext()) {
length1 ++;
h1 = h1.getNext();
}
while(null != h2.getNext()) {
length1 ++;
h2 = h2.getNext();
}
return length1>=length2?getNode(h1,length1,h2,length2):getNode(h2,length2,h1,length1);
}
这是最乐观的一种情况，但是还需要考虑链表上存在环的情况。那么还需要添加一个方法，判断链表上是否存在环。
对于如何判断链表上是否存在环，解决办法是采用快慢指针，两个指针P1、P2分别指向同一个链表的头节点，之后，P1一次前进两个节点，P2一次前进一个节点。如果最终P1和P2能重合，则说明一定存在交点。反之如果最终P1或者P2存在一个为空的情况，则说明这两个链表不相交。
/**
* 判断是否存在环
* 步骤：设置两个指针同时指向head，其中一个一次前进一个节点（P1），另外一个一次前进两个节点(P2)。
* p1和p2同时走，如果其中一个遇到null，则说明没有环，如果走了N步之后，二者指向地址相同，那么说明链表存在环。
* @param h
* @return
*/
public static boolean isLoop(DataNode h) {
DataNode p1 = h;
DataNode p2 = h;
while(p2.getNext() != null && p2.getNext().getNext()!=null){
p1 = p1.getNext();
p2 = p2.getNext().getNext();
if(p1 == p2)
break;
}
return !(p1==null||p2==null);
}
因此上述问题还有另外一个解法，将其中一个链表首尾相连，检测另外一个链表是否存在环，如果存在（该环就是首尾相连的链表），则两个链表相交，而检测出来的依赖环入口即为相交的第一个点。需找出环的入口，设置p1,p2两个指针，同样一个走一步一个走两步，两者相遇则必在环上某一点相遇，记下此位置p1=p2，在p1和p2重合后，设置一个p3指向表头，然后p1和p3每次同时行走一步，每步前进一个节点，等到p1和p3重合时，重合的位置就是环的入口。
参考csdn上的一张图：
设L1为无环长度，L2为环长，a为两指针相遇时慢速指针在环上走过的距离，而且a一定小于环总长L2（这是因为当慢速指针刚进入环时，快速指针已经在环中，且距离慢速指针的距离最长为L2-1，需要追赶的距离为L2-1，即刚好在慢速指针的下一个节点，需要几乎一整圈的距离来追赶，赶上时，慢速指针也不能走完一圈）。此时设慢速指针走过的节点数为N，则可列出：
快速指针走过的节点数为： 2N = L1 + k * L2 + a； （这里快速指针走过的节点数一定是慢速指针走过的2倍）。
慢速指针走过的节点数为： N = L1 + a；
则相减可得， N = k * L2 , 于是得到 k * L2 = L1 + a; 即， L1 = (k-1) * L2 + (L2 - a) （这里k至少是大于等于1的，因为快速指针至少要多走一圈）
即 L1的长度 = 环长的整数倍 + 相遇点到入口点的距离， 此时设置头结点p3, 与p1同时，每次都走一步，相遇点即为入口点。
/**
* 方法二： 将其中一个链表首尾相连 从另外一个链表开始，检测是否存在环，如果存在，则说明二者相交。
* 如果需要找出环的入口，则设P1 P2 两个指针，P1一次走两步，P2一次走一步，两者在环上某一点相遇。记下此位置。
* 此时设置一个指针P3指向表头，然后P1和P3每次同时行走一步，每步前进一个节点。等到P1、P3重合时，则重合位置即使环入口。
* @param h1
* @param h2
* @return
*/
public DataNode entryNoLoop(DataNode h1,DataNode h2) {
DataNode p = h1;
while(null != p.getNext()){
p = p.getNext();
}
p.setNext(h1);
return entryLoop(h2);
}
/**
* 获取环的入口点
* @param h
* @return
*/
public DataNode entryLoop(DataNode h) {
DataNode p1 = h;
DataNode p2 = h;
DataNode p3 = h;
while(null != p2.getNext() && null != p2.getNext().getNext()){
p1 = p1.getNext();
p2 = p2.getNext().getNext();
if(p1 == p2)
break;
}
while(p3 != p1) {
p1 = p1.getNext();
p3 = p3.getNext();
}
return p3;
}
2.两个链表均存在环
对于连个链表均存在环的情况，相交点要么在环上，要么在环外。
无论上述何种情况，均需要首先分别找到各自到环的入口点。解法可以即使上述entryLoop方法。
在得到环的入口点之后，各自判断环的入口点是否相同，如果如口点相同，则为左图描述情况，因此只需计算着两个链表到入口点部分长度之差，然后用长的部分减去差，再同时与短的部分同步前进，如果节点相同，则为相交点。反之如果入口点不同，则相交点为这两个链表的任意一个入口点。
/**
*
* @param h1
* 链表1的头节点
* @param l1
* 链表1的环入口
* @param h2
* 链表2的头节点
* @param l2
* 链表2的头节点
* @return
*/
public static DataNode bothLoop(DataNode h1, DataNode l1, DataNode h2, DataNode l2) {
DataNode p1 = null;
DataNode p2 = null;
if (l1 == l2) {
p1 = h1;
p2 = h2;
int n = 0;
while (p1 != l1) {
n++;
p1 = p1.getNext();
}
while (p2 != l2) {
n--;
p2 = p2.getNext();
}
p1 = n > 0 ? h1 : h2;
p2 = p1 == h1 ? h2 : h1;
n = Math.abs(n);
while (n != 0) {
n--;
h1 = h1.getNext();
}
while (p1 != p2) {
p1 = p1.getNext();
p2 = p2.getNext();
}
return p1;
} else {
p1 = l1.getNext();
while (p1 != l1) {
if (p1 == l2) {
return l1;
}
}
return null;
}
}
/**
*
* @param h1
* @param h2
* @return
*/
public DataNode getJoinNode(DataNode h1, DataNode h2) {
if (null == h1 || null == h2)
return null;
DataNode l1 = entryLoop(h1);
DataNode l2 = entryLoop(h2);
if (null == l1 && null == l2)
return getFirstJoinNode(h1, h2);
if (null != l1 && null != l2)
return bothLoop(h1,l1,h2,l2);
return null;
}
