寻找两个链表相交节点方法（可以是有环链表）

问题分析：两个链表相交可以分为两个大类，一是两个无环链表相交，二是两个有环链表相交。

无环相交如图：

有环相交有两种情况，一种是 先相交后成环，如图：

另一种是交点有两个，是成环后的交点（入环节点不同）

方法

1.判断链表是否有环，返回第一个入环节点。
2.判断是否相交
3.判断相交节点是否相同

判断链表是否有环，并返回第一个入环节点

使用快慢指针，快指针一次走两步，慢指针一次走一步，如果链表有环则两个指针必然会相遇。具体细节参考判断链表是否有环

无环链表相交问题

1.判断两个链表是否同时无环
2.先遍历两个链表获得链长lensA和lensB
3.让长链表先走abs(lensA - lensB)步，之后两个链表共同前进，如果在遍历链表结束之前有相同节点，则两个链表相交。

两个有环链表相交问题

1.判断两个链表是否同时有环
2.判断链表第一个入环节点是否相同。
3.如果相同，则使用无环链表相交问题类似的方法，只是将链表遍历终点定在入环节点
3.如果不相同，则从链表A开始遍历，如果遍历过程中遇见了链表B的入环节点则链表相交。
代码如下：

public class FindFirstIntersectNode {
//定义节点public static class Node {public int value;public Node next;public Node(int data) {this.value = data;}}public static Node getIntersectNode(Node head1, Node head2) {if (head1 == null || head2 == null) {return null;}//判断链表是否有环，有就返回环节点Node loop1 = getLoopNode(head1);Node loop2 = getLoopNode(head2);//都无环，采用无环相交方法if (loop1 == null && loop2 == null) {return noLoop(head1, head2);}//都有环，采用有环相交方法if (loop1 != null && loop2 != null) {return bothLoop(head1, loop1, head2, loop2);}return null;}// 快慢指针方法，找到链表第一个入环节点，如果无环，返回nullpublic static Node getLoopNode(Node head) {if (head == null || head.next == null || head.next.next == null) {return null;}// n1 慢  n2 快Node n1 = head.next; // n1 -> slowNode n2 = head.next.next; // n2 -> fastwhile (n1 != n2) {if (n2.next == null || n2.next.next == null) {return null;}n2 = n2.next.next;n1 = n1.next;}//相遇时，快指针返回头结点，每次走一步n2 = head; // while (n1 != n2) {n1 = n1.next;n2 = n2.next;}return n1;}// 如果两个链表都无环，返回第一个相交节点，如果不想交，返回nullpublic static Node noLoop(Node head1, Node head2) {if (head1 == null || head2 == null) {return null;}Node cur1 = head1;Node cur2 = head2;int n = 0;while (cur1.next != null) {n++;cur1 = cur1.next;}while (cur2.next != null) {n--;cur2 = cur2.next;}if (cur1 != cur2) {return null;}// n  :  链表1长度减去链表2长度的值cur1 = n > 0 ? head1 : head2; // 谁长，谁的头变成cur1cur2 = cur1 == head1 ? head2 : head1; // 谁短，谁的头变成cur2n = Math.abs(n);while (n != 0) {n--;cur1 = cur1.next;}while (cur1 != cur2) {cur1 = cur1.next;cur2 = cur2.next;}return cur1;}// 两个有环链表，返回第一个相交节点，如果不想交返回nullpublic static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {Node cur1 = null;Node cur2 = null;//入环节点相同if (loop1 == loop2) {cur1 = head1;cur2 = head2;int n = 0;while (cur1 != loop1) {n++;cur1 = cur1.next;}while (cur2 != loop2) {n--;cur2 = cur2.next;}cur1 = n > 0 ? head1 : head2;cur2 = cur1 == head1 ? head2 : head1;n = Math.abs(n);while (n != 0) {n--;cur1 = cur1.next;}while (cur1 != cur2) {cur1 = cur1.next;cur2 = cur2.next;}return cur1;} else {//入环节点不同cur1 = loop1.next;while (cur1 != loop1) {if (cur1 == loop2) {return loop1;}cur1 = cur1.next;}return null;}}
}