问：
给定两个可能有环也可能无环的单链表，头节点head1和head2。请实现一个函数，如果两个链表相交，请返回相交的第一个节点；如果不相交，返回null。如果两个链表长度之和为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1)
答：
首先解决环的问题，如何判断一个链表有没有环。写一个函数，如果有环就返回入环的第一个节点，无环则返回空。
(1) 使用哈希表
初始化一个HashSet存储已经遍历过的节点，依次将abcde加入set中，当回到c时发现c已经在集合中，那么c为入环的节点
(2) 快慢指针
快指针一旦走到空，链表一定没有环。如果有环，快慢指针一定会在环上相遇
接下来快指针移至开头，每个指针一次只走一步，最终会在入环节点相遇
发现快指针移动至入环节点需要4步，慢指针同样需要4步，二者相遇
public static Node getLoopNode(Node head) {if (head == null || head.next == null || head.next.next == null) {return null;}Node slow = head.next;Node fast = head.next.next;while (slow != fast) {if (fast.next == null || fast.next.next == null) {return null;}fast = fast.next.next;slow = slow.next.next;}fast = head;while (slow != fast) {slow = slow.next;fast = fast.next;}return slow;
}对两个链表分别调用这个方法，能找出各自的入环节点，最后有3种情况
1.loop1 == null && loop2 == null
两个单链表都是无环的
遍历第一个链表，从head1一直遍历到它的最后一个节点end1，记录长度为len1假设100
遍历第二个链表，从head2一直遍历到它的最后一个节点end2，记录长度为len2假设80
先判断end1和end2的内存地址是否相同，如果不相同，那么head1和head2不可能相交；如果相同，head1先走20步，然后head2出发一起走，二者一定会在第一个相交节点相遇
2.loop1与loop2只有一个null
不相交
3.loop1与loop2全不为null
(1) loop1 == loop2
认为loop1和loop2就是终止节点，调用上面loop全为null的方法
(2) loop1 != loop2
分为两种情况
-
a
-
b
让loop1继续往下走，如果在回到自己的路程中能遇到loop2就是情况a，否则为情况b
在情况a中loop1和loop2都可以被视为第一个相交的节点
public 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;}
}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;
}
