两个单向链表是否相交汇总

投了腾讯IOS客户端开发岗&＃xff0c;结果面试官大大问了一堆操作系统&＃xff0c;数据结构&＃xff0c;算法&＃xff0c;计算机网络问题&＃xff0c;orz&＃xff0c;给大神跪了&＃xff01;最后问大神什么职位&＃xff0c;大神说他就是IOS工程师。真服了&＃xff01;当时问了算法&＃xff0c;关于链表&＃xff0c;当时没想起来&＃xff0c;面完之后拿个纸算算&＃xff0c;我竟然会。写下来&＃xff0c;mark一下。

 

问题&＃xff1a;给出两个单向链表的头节点&＃xff0c;判断两个链表是否相交&＃xff0c;如果相交&＃xff0c;请找出相交节点。

这个问题是分好几种情况的&＃xff0c;要分支来判断&＃xff1a;

假定两个单链表分别为链表A和链表B&＃xff0c;则&＃xff1a;

1.A无环&＃xff0c;B无环&＃xff0c;存在以下三种情况&＃xff1a;

　　&＃xff08;1&＃xff09;. &＃xff08;2&＃xff09;. &＃xff08;3&＃xff09;.

2.A有环&＃xff0c;B无环(A无环&＃xff0c;B有环亦然)&＃xff0c;存在一种情况&＃xff1a;

               

3.A有环&＃xff0c;B有环&＃xff0c;则存在三种情况&＃xff1a;

　　&＃xff08;1&＃xff09;. &＃xff08;2&＃xff09;. &＃xff08;3&＃xff09;.

判断一个单向是否有环的方法&＃xff1a;从该链表头指针开始&＃xff0c;设置两个指针&＃xff0c;一个快指针&＃xff0c;一个慢指针。快指针每次沿着链表走两个链节&＃xff0c;慢指针每次沿着链表走一个链节&＃xff0c;当两个指针指向同一个链节时&＃xff08;即两个指针相等&＃xff09;&＃xff0c;说明链表有环&＃xff1b;当快指针指向null时&＃xff0c;说明链表无环。

对于情况1&＃xff1a;

　　　　分别遍历得到两个链表的长度&＃xff0c;并且在遍历的时候&＃xff0c;比较两个链表的终节点&＃xff0c;如果不同&＃xff0c;则是(2)&＃xff1b;如果相同&＃xff0c;则为(1)或(3).

　　　　对(1)(3),取链表节点数的差值&＃xff0c;将长链表从差值处开始遍历&＃xff0c;短节点从头结点开始遍历&＃xff0c;比较两个节点是否相等&＃xff0c;不相等继续向下遍历&＃xff0c;直至相等找到相交节点。

对于情况2&＃xff1a;

　　　　直接得出结论&＃xff0c;二者不相交。

对于情况3&＃xff1a;

　　　　判断A有环的因为快慢指针指向了同一个节点&＃xff0c;记为交点A&＃xff0c;B的记为交点B。从交点A放出一个慢指针&＃xff0c;每次沿链表走一个链节&＃xff1b;交点B放出一个快指针&＃xff0c;每次沿着链表走

　　　　两个链节。当两个指针相交&＃xff0c;则说明A、B共用一个环&＃xff0c;情形为(2)或(3)&＃xff1b;当A的慢指针走回交点A&＃xff0c;两个指针仍然没相交&＃xff0c;说明情况为(1).

　　　　对(2)(3),将交点A的next指向null&＃xff0c;断开环路然后按照1(3)中的线性查找方法去找相交节点&＃xff0c;一定能找到一个交点C。

　　　　我们将交点A的next复原&＃xff0c;从交点C开始遍历&＃xff0c;找到交点C的前节点&＃xff0c;让交点C前节点的next指向null&＃xff0c;这个时候能够找到交点D。当交点C与交点D相同时&＃xff0c;为情况(2);不

　　　　相等时为情况(3).