两个单链表相交问题3——有环链表相交

题目：如何判断两个有环链表相交，相交则返回第一个相交的节点，否则直接返回NULL
此时已知两个链表都一个自己的第一个入环节点，假设链表1的第一个入环节点是loop1，链表2的第一个入环节点是loop2，

解题步骤：
（1）如果loop1 == loop2，则两个链表的结构如下

（2） 如果loop1 != loop2,两个链表不相交的结构有2种，一种是彻底不相交如图1，一种是环的入口不同如图2

让链表1从入口点loop1出发遍历，如果回到loop1之前没有遇到loop2，则表示的是图1情况，即不相交，返回NULL。如果回到loop1之前遇到loop2，则是图2情况，返回loop1或者loop2。

代码：

node* bothLoop(node* head1, node8 loop1, node* head2, node* loop2){node* p1 = NULL;node* p2 = NULL;if(loop1 == loop2){p1 = head1;p2 = head2;int len = 0;while(p1 != loop1){len++;p1 = p1->next;}while(p2 != loop2){len--;p2 = p2->next;}p1 = len > 0 ? head1 : head2;p2 = (p1 == head1) ? head2 : head1;len = abs(len);while(len != 0){len--;p1 = p1->next;}while(p1 != p2){p1 = p1->next;p2 = p2->next;}return p1;}else{p1 = loop1->next;while(p1 != loop1){if(p1 == loop2){return loop1;}p1 = p1->next;}return NULL;}
}