数据结构—判断两个链表是否相交，寻找两个链表的相交节点_判断两链表是否相交

【题目】

判断两个链表（链表可以有环，可以无环）是否相交，若相交，则返回相交节点，不相交则返回null

1.判断两个链表是否相交

【思路】

两个链表分三种情况：

①两个链表均为非环链表；

②两个链表一个为环，一个非环；

③两个链表均为环

第一种情况非环链表根据链表的定义，只需比较两个链表尾节点是否相同，若相同则一定相交，不同则一定不相交；

第二种情况由于链表的next指针永远只指向一个节点，所以若环链表与非环链表相交非环链表一定为环，所以此情况一定两个链表不相交；

第三种情况又可以分为三种情况：1.两个环链表不相交；2.两个环链表在结环点之前相交；3.两个链表在环上相交

此时只需找到某一链表b的结环节点，在另一链表a遍历自己至第二次到自己结环点的时候此时链表a一定遍历了自身所有节点，判断a链表有无节点与b链表相遇，若相遇，则两环链表相交，若不相遇，则说明一定不相交。

设计一个处理链表的工具类NodeListUtils

判断链表是否为环的方法：

/**
	 * 判断链表是否有环
	 * @param nodeList
	 * @return
	 */
	public static <T> boolean isRing(NodeList<T> nodeList) {
		Node<T> head = nodeList.head;
		Node<T> fast = head;
		Node<T> slow = head;
		while (fast != null && fast.next != null) {
			fast = fast.next.next;
			slow = slow.next;
			if (fast == slow) {
				return true;
			}
		}
 
		return false;
	}

获取非环单链表尾节点的方法：

/**
	 * 获取单链表的最后一个节点
	 * 
	 * @param nodeList
	 * @return
	 */
	public static <T> Node<T> getLastNode(NodeList<T> nodeList) {
		if (no