两个单链表相交问题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;
	}
}