【题目】
? 单链表可能有环，可能无环头节点 head1 和 head2， 这两个链表可能相交,也可能不相交。请实现一个函数， 如果两个链表相交， 请返回相交的第一个节点； 如果不相交， 返回 null 即可。
?如果链表1的长度为N，链表2的长度为M，时间复杂度请达到O(N + M)，额外的空间复杂度请达到O(1)。
【解答】
三个子问题，具体如下。
? 问题一：如何判断一个链表是否有环，如果有，返回第一个进入环的节点，没有则返回null。
? 问题二：如何判断两个无环链表是否相交，相交则返回第一个相交节点，不相交则返回null。
? 问题三：如何判断两个有环链表是否相交，相交则返回第一个相交节点，不相交返回null。
? 注意：一个链表有环，一个无环，二者不可相交，直接返回null。
package base;public class P69_NodeCross {/*** 获取入环节点* @param node1 节点1* @param node2 节点2* @return*/public static Node getCrossNode(Node node1, Node node2) {if (null == node1 || null == node2) {return null;}// 查看是否有环Node loop1 = isCircle(node1);Node loop2 = isCircle(node2);// 1、无环相交if (null == loop1 && null == loop2) {return noCircleCross(node1, node2);}// 2、有环相交if (loop1 != null && loop2 != null) {return nodeCross(node1, loop1, node2, loop2);}return null;}// 设置一个快慢指针，如果链表有环，那么快指针和慢指针一定会在环中的某个位置相遇，当快指针和慢指针相遇时，快指针重新回到head位置,// 改为每次移动一步，慢指针依然一次移动一步；快慢指针再次相遇的位置，就是入环节点public static Node isCircle(Node node) {if (node.next == null || node.next.next == null) {return null;}Node slow = node.next;Node fast = node.next.next;while (slow != fast) {if (fast.next == null || fast.next.next == null) {return null;}slow = slow.next;fast = fast.next.next;}fast = node;while (slow != fast) {fast = fast.next;slow = slow.next;}return fast;}/*** 无环相交* 如果两个无环节点相交，那么从相交节点开始，一直到两个链表终止的这一段，是连个链表共享的* @param head1* @param head2* @return*/public static Node noCircleCross(Node head1, Node head2) {int n = 0;Node node1 = head1;while (node1 != null) {node1 = node1.next;n++;}Node node2 = head2;while (node2 != null) {node2 = node2.next;n--;}// node1 为长度较长节点node1 = n > 0 ? head1 : head2;node2 = node1 == head1 ? head2 : head1;n = Math.abs(n);// node1 先走n步，然后两个链表一起走，两个链表第一次走到一起的节点就是第一个相交节点while (n > 0) {n--;node1 = node1.next;}while (node1 != null && node2 != null) {if (node1 == node2) {return node1;}node1 = node1.next;node2 = node2.next;}return null;}/*** 有环相交* @param head1 节点1* @param loop1 入环节点1* @param head2 节点2* @param loop2 入环节点2* @return*/public static Node nodeCross(Node head1, Node loop1, Node head2, Node loop2) {// 如果入环节点相等if (loop1 == loop2) {int n = 0;Node node1 = head1;while (node1 != loop1) {node1 = node1.next;n++;}Node node2 = head2;while (node2 != loop2) {node2 = node2.next;n--;}node1 = n > 0 ? head1 : head2;node2 = node1 == head1 ? head2 : head1;n = Math.abs(n);while (n > 0) {n--;node1 = node1.next;}while (node1 != node2) {node1 = node1.next;node2 = node2.next;}return node1;} else {Node temp1 = loop1.next;while (temp1 != loop1) {if (temp1 == loop2) {return loop2;}temp1 = temp1.next;}}return null;}
}