求两个链表是否相交并求出相交点
一、问题描述
有两个链表，判断是否相交并求出相交的点？
二、问题分析
大家看到题目会不由自主的想起一个很普遍的情况，就是下面
但是这个题目有一个陷阱就是,没有讲明两个链表的结构，没有很好地给出，其实有三种情况
（1）当两个链表都无环，如上面
（2）当一个链表有环，另一个链表无环
（3）当两个链表都有环
这三种情况，下面一一讲解这些情况下两个链表是否相交以及相交点。
三、问题解析
（一）当两个链表都无环
3.1 方法1
链表相交后，发现后面的结点全部公用，我们可以这样：从两个链表的头走到尾，判断链尾地址信息是不是一样，如果是则相交，反之则不交即可。
Node* LinkList::findByIndex(int index){ //根据索引返回节点信息 Node* p = head; int i = 0; if (index<0||index >getLength()) { cout << "索引非法！" << endl; return NULL; } while (p) { if (i == index) return p; else { p = p->next; i++; } } return NULL; } bool LinkList::isIntersect(LinkList preLinkList, LinkList forLinkList) { Node* tail1 = preLinkList.findByIndex(preLinkList.head->value);//链表1尾部 Node* tail2 = forLinkList.findByIndex(forLinkList.head->value);//链表2尾部 if (tail1 == tail2) { return true; } return false; }
3.2 方法二
我们可以根据上图，相交之后部分的长度是一样的，相等的，所以我们可以这样让长链表的长度减去稍微较短的长度，得到两个链表的相差长度，再让长链表从头结点开始遍历这个长度，与此同时，短链表也向后走，若指针相等，链表就相交，反之，则不交
bool LinkList::isIntersect(LinkList preLinkList, LinkList forLinkList) { bool flag = false; if (preLinkList.head->value > forLinkList.head->value) flag = true; int length = abs(preLinkList.head->value - forLinkList.head->value);//相差的长度 Node* p= preLinkList.head->next, *q= forLinkList.head->next;//此处初始化应对length=0的情况 if (length) { if (flag) {//第一个链表长 p = preLinkList.findByIndex(length)->next; q = forLinkList.head->next; } else { p = forLinkList.findByIndex(length)->next; q = preLinkList.head->next; } } while (p != q) { //若指针相等跳出 ，可能会同时为空 p = p->next; q = q->next; } if (p) //排序跳出时为空 return true; else return false; }
求相交点
Node* LinkList::findIntersectPoint(LinkList preLinkList, LinkList forLinkList){ //不带环的链表求交点
bool flag = false;
if (preLinkList.head->value > forLinkList.head->value)
flag = true;
int length = abs(preLinkList.head->value - forLinkList.head->value);//相差的长度
Node* p= preLinkList.head->next, *q= forLinkList.head->next;//此处初始化应对length=0的情况
if (length) {
if (flag) {//第一个链表长
p = preLinkList.findByIndex(length)->next;
q = forLinkList.head->next;
}
else {
p = forLinkList.findByIndex(length)->next;
q = preLinkList.head->next;
}
}
while (p != q) { //若指针相等跳出 ，可能会同时为空
p = p->next;
q = q->next;
}
if (p) //排序跳出时为空
return p;
else
return NULL;
}
（二 ）当一个链表不带环，另一个带环
如果一个链表不带环，另一个链表带环，两个链表一定没有相交点。因为相交之后，链表肯定有部分是共用，若有环，都会带环，而且环的长度一样，相交点也是环的入口处。
（3）两个都带环
就有两种情况，一种交于环外，另外是交与环内，如下图
图1
图2
通过上图2发现，如果把环看成链表1的，则链表2相交于B点，反过来把环看出链表2的，则链表1相交于A处，所以你看的B处和A处，只是视觉上的，如果环是两个链表的，则相交于环的任何结点上。
思路：
（1）因为环是大家共用的，我们先求出两个链表的差L，也就是环外的差，并获得链表的环入口点
（2）让一个较长的链表从开始走过L个结点
（3）然后再让短的链表从头开始与之同步移动，保证两个链表不走到环的入口时，判断结点地址是否相同
（4）若出现相同而且未到入口，则返回交点，交于环外
（5）反之，直接返回链表的入口即可。
Node* LinkList::findIntersectPoint(LinkList preLinkList, LinkList forLinkList){ //带环链表求交点
int length1 = preLinkList.getCircleLinklistLength();
int length2 = forLinkList.getCircleLinklistLength(); //获得每个链表总长度
Node* preEntry = preLinkList.findEnterCircle();
Node* forEntry = forLinkList.findEnterCircle(); //找到每个的环入口点
int length;
Node* pre = preLinkList.head->next;
Node* forth = forLinkList.head->next; //初始化各自链表的第一个节点的指针
if (length1 > length2) { //根据谁长谁短 决定谁后移指针
length = length1 - length2;
for (int i = 1;i <= length;pre = pre->next, i++);
}
else {
length = length2 - length1;
for (int i = 1;i <= length;forth = forth->next, i++);
}
while (pre != preEntry&&forth != forEntry&&pre != forth) { //向后移，注意是否走到环入口点
pre = pre->next;
forth = forth->next;
}
/*结束循环的3种情况
1.=====2个链表任意一个或全部同时走到了环入口点，结束了循环
2.======2个链表任意一个或全部同时走到了环入口点，并且pre=forth，结束了循环
3.======没有到达任何一个环入口点，pre=forth结束了循环
*/
if (pre == forth) //对应情况2、3，如果是情况2，说明2个链表的环入口点相同；如果情况3，则说明在任何一个环入口之前找到了相交点
return pre;
else
return preEntry;//对应情况1
}
以上就是链表的相交和相交点的思考，准备去BAT面试的大佬，还是可以读一下的。