两个链表寻找第一个相交节点，我们要先判断两个链表是否有环。

我们如何判断链表有没有环呢？

我们可以用快慢指针来判断链表是否有环：

思路：

        我们让快指针一次走两步，慢指针一次走一步，如果快指针走到了空节点那么就证明这个链表是没有环的，那我们根据什么来判断链表有环呢，如果快指针跟满指针在走的时候相遇了就代表这个链表是有环的。既然有环，那我们就需要将入环节点给找出来，我们现将慢指针放在与快指针相遇的地方不动，然后将快指针放到第一个节点，然后两个指针都一步一步的走，相遇的节点即为入环节点。

以下为寻找入环节点的代码：

LNode GetLooopNode(LNode l){
	if(l == NULL || l->next->next ==NULL || l->next == NULL){
		return ;	
	}
	//如果链表的节点数少于3个的话直接返回NULL 
	LNode fast = l->next->next;				//初始化快指针	
	LNode slow = l->next;					//初始化慢指针 
	while(fast != slow){					//当快指针没有没遇到慢指针的时候循环  
		if(fast->next == NULL || fast->next->next == NULL){
			return NULL;					//如果快指针后面是空节点就返回NULL 
		}						
		fast = fast->next->next;
		slow = slow->next;
	}
	fast = l;								//将快指针重置为l 
	while(fast != slow){					//当快指针没有遇到慢指针的时候循环 
		fast = fast->next;					
		slow = slow->next;
	}
	return fast;
}

入环节点寻找完毕了，我们就可以开始去寻找两个链表的相交节点了。

链表寻找相交节点我们可以分为以下三种情况

设有链表L1和链表L2。

1、两个链表都没有环:

        将他们遍历到尾结点并对长度进行计数。如果L1和L2的尾结点不同证明他们不相交，如果相同，我们就把L1和L2的长度相减得到他们的差值n，让长的那个链表遍历n次，然后两个链表同时遍历，直到遇见两个节点相等的情况直接返回该节点，该节点即为两个链表的第一个相交节点。

2、两个链表都有环：

        情形一：

        他们的入环节点相同，入环节点相同我们就将循环节点作为他们的终止节点，对两个链表同时遍历，然后当做两个链表都没有环的情况来看待，就能求出他们的第一个相交节点。

       情形二：

        他们的入环节点不相同，我们先从L1的入环节点开始遍历，当再次到达环节点之前，如果碰到了L2的入环节点即两个链表的第一个相交节点就出现了。否则两个链表没有相交节点。

3、一个链表链表有环，一个链表无环：

        一个链表有环一个链表无环，他们之间必定没有相交节点。

以下是判断代码：   

typedef struct Link{
	int data;
	struct Link *next;
	
}Node,*LNode;
//找到链表的第一个环节点，如果没有，则返回NULL 
LNode GetLoopNode(LNode L){
	if(L == NULL || L->next == NULL || L->next->next == NULL)
		return NULL;
	//如果链表的节点数不大于3个则直接返回空 
	LNode fast = L->next->next;				//定义fast为快指针并指向L的第二个节点 
	LNode slow = L->next; 					//定义slow为慢指针并指向L的第一个节点 
	while(fast != slow){					//如果快慢指针指向同一个地址则表明链表L存在环 
		if(fast->next->next == NULL || fast->next == NULL)
			return NULL;					
            //如果快指针后面指向NULL的话证明链表L不存在环，直接返回空	 
		fast = fast->next->next;			//快指针一次走两步 
		slow = slow->next;					//慢指针一次走一步 
	}
	fast = L;								//将快指针放回第一个节点 
	while(fast != slow){					//如果快指针和慢指针没有相遇的话就循环 
		fast = fast->next;					//快指针与慢指针每次走一步 
		slow = slow->next;
	}
	return fast;
} 

//两个无环的链表找相交节点
LNode NoLoop(LNode L1,LNode L2){
	if(L1 == NULL || L2 == NULL)			//如果L1和L2为空，直接返回NULL 
		return NULL;
	LNode p = L1;
	LNode q = L2;					
	int n = 0;
	//只使用一个n变量，在统计完两个链表的长度之后，n的值就是他们长度之间的差值 
	while(p->next != NULL){					//对L1的长度进行计数				
		n++;
		p = p->next;
	}
	while(q->next != NULL){					
		n--;								//对L2的长度进行计数 
		q = q->next;
	}
	if(p != q)								//如果p不等于q证明两个链表没有相交，否则相交 
		return NULL;
	p = n > 0 ? L1 : L2;					//把p指向两个链表中长度更长的那一个 
	q = p == L1 ? L2 : L1;					//把q指向两个链表中长度更笑的那一个 
	n = fabs(n);
	while(n){        //将p向前移动n个节点，使得p和q能够在向前遍历的时候相遇 
		n--;
		p = p->next;
	}
	while(p != q){							//如果p和q没有相交，循环继续，否则返回p	 
		p = p->next;
		q = q->next;
	}
	return p;
} 
 
//两个有环的链表寻找相交节点：
//如果两个链表的入环节点相同，将循环节点作为他们的中止节点
//因为两个链表的入环节点是相同的，所以他们的相交节点必定在入环节点以前 
//我们直接将链表的环除开以后就相当于无环的链表
//因此我们可以用求无环链表的相交节点的方法求两个链表入环节点相同的相交节点
LNode bothLoop(LNode L1,LNode loop1,LNode L2,LNode loop2){
	LNode q = NULL;
	LNode p = NULL;
	if(loop1 == loop2){			            //判断L1和L2的入环节点是否相同
		p = L1;				    
		q = L2;								 
		int n = 0 ;							
		while(p != loop1){             
			n++;
			p = p->next;
		}
		while(q != loop2){
			n--;
			q = q->next;
		}
		p = n > 0 ? L1 : L2;				
		q = L1 == p ? L2 : L1;
		n = fabs(n);
		while(n){
			n--;
			p = p->next;
		}
		while(p != q){
			p = p->next;
			q = q->next;	
		}
		return p;
	}
	else {									//如果两个相交节点的入环节点不一样 
		p = loop1->next;					//从第一个链表的环节点的下一个节点开始遍历 
		while(p != loop1){					
        //在到达环结点之前如果没有与第二个链表的话环节点相交则证明：
			if(p == loop2){					//两个链表没有相交节点 ，否则直接返回相交节点 
				return p;
			}
			p = p->next;
		}
		return NULL;
	}	
} 

LNode GetNode(LNode l1,LNode l2){
	if(l1 == NULL || l2 == NULL){			//两个表有一个表为空返回NULL 
		return NULL;
	}
	LNode loop1 = GetLoopNode(l1);			//分别求出两个表的环节点 
	LNode loop2 = GetLoopNode(l2);
	if(loop1 == NULL && loop2 == NULL){		//两表都没有环 
		return NoLoop(l1,l2);
	}
	if(loop1 !=NULL && loop2 != NULL){		//两个表都有环 
		return bothLoop(l1,loop1,l2,loop2);
	}
	return NULL;
}