若两个链表相交，请返回相交的第一个节点。

给定两个有可能有环也有可能无环的单链表，头节点head1和head2。

实现一个函数，如果两个链表相交，请返回相交的第一个节点（从这个节点开始，后续结构都一样）。如果不相交，返回null。

复杂度要求：

• 如果两个链表长度之和为N，要求：时间复杂度为O(n)，额外空间复杂度为O(1)。

该题目可以理解为LeetCode 160. 相交链表的升级版，因为LeetCode160题中的链表是无环的，所以就简单了很多！！

思路

既然两个链表head1、head2可能有环，也可能无环，我们先判断这两个链表到底是不是有环链表，这是会有三种情况：

• 一个链表有环、一个链表无环。
• 两个链表都无环。
• 两个链表都有环。

第一种情况（一个链表有环、一个链表无环）最简单，两个链表肯定不相交。

第二种情况（两个链表都无环），判断两个链表长度的差值x，长的链表先往后走x步，然后再让两个链表一起往后走，如果两个链表当前节点不相等就一直到往后走，直到走到链表尾部。

第三种情况（两个链表都有环），最复杂，其中又细分三种情况。

1> 第一种情况：两个链表不相交，各玩个的。
2> 第二种情况：两个链表相交了，相交节点在入环节点 及其之前（即：入环节点是同一个）。则以入环节点为尾，计算前面链表的长度；然后再和无环链表相交一样处理。

• 入环节点的查找方式：

  • 快慢指针法，快慢指针同时从head出发，判断出链表是有环链表。
  • slow从相交节点开始继续走、fast节点放到head继续往后走，都每次走一步，则它俩相遇的节点是链表环的第一个节点。
    3> 第三种情况：两个链表相交了，但入环节点不是同一个；

• 假设head1的入环节点为loopNode1，head2的入环节点为loopNode2。
• 从loopNode1开始在环里转，如果能遇到loopNode2，返回loopNode1；
• 如果都转了一圈了，也找不到loopNode2，那就是两个链表不相交。
• 注意：可以返回loopNode1，也可以返回loopNode2。

代码

/*** 方法二：不使用容器* 时间复杂度为O(n)，额外空间复杂度为O(1)。*/
public static ListNode getIntersectNode(ListNode head1, ListNode head2) {if (head1 == null || head2 == null) {return null;}// head1's first into loop nodeListNode loopNode1 = getLoopNode(head1);ListNode loopNode2 = getLoopNode(head2);// both no_loopif (loopNode1 == null && loopNode2 == null) {return noLoop(head1, head2);}// both loopif (loopNode1 != null && loopNode2 != null) {/*** 几种情况：*     1) 两个链表不相交，各自玩自己的*     2) 两个链表相交了，相交节点在入环节点 及其之前（即：入环节点是同一个）。*           以入环节点为尾，计算前面链表的长度，然后和无环链表相交一样处理。*     3）两个链表相交了，入环节点不是同一个*         从loopNode1开始在环里转，如果能遇到loopNode2，返回loopNode1；如果都转了一圈了，也找不到loopNode2，那就是两个链表不相交*         可以返回loopNode1，也可以返回loopNode2*/return bothLoop(head1, loopNode1, head2, loopNode2);}// one loop another no_loopreturn null;
}private static ListNode noLoop(ListNode head1, ListNode head2) {// n -> head1 and head2 's count of difference nodesint n = 0;ListNode curr1 = head1;ListNode curr2 = head2;while (curr1.next != null) {n++;curr1 = curr1.next;}while (curr2.next != null) {n--;curr2 = curr2.next;}// tail node is different ，must not intersectif (curr1 != curr2) {return null;}// head1 and head2 who more long who curr1, else curr2curr1 = n > 0 ? head1 : head2;curr2 = curr1 == head1 ? head2 : head1;n = Math.abs(n);while (n > 0) {n--;curr1 = curr1.next;}while (curr1 != curr2) {curr1 = curr1.next;curr2 = curr2.next;}return curr1;
}/*** both head is loop** @param loop1 head1's first into loop node* @param loop2 head2's first into loop node*/
private static ListNode bothLoop(ListNode head1, ListNode loop1, ListNode head2, ListNode loop2) {if (loop1 == loop2) {int n = 0;ListNode curr1 = head1;ListNode curr2 = head2;while (curr1 != loop1) {n++;curr1 = curr1.next;}while (curr2 != loop2) {n--;curr2 = curr2.next;}// head1 and head2 who more long who curr1, else curr2curr1 = n > 0 ? head1 : head2;curr2 = curr1 == head1 ? head2 : head1;n = Math.abs(n);while (n > 0) {n--;curr1 = curr1.next;}while (curr1 != curr2) {curr1 = curr1.next;curr2 = curr2.next;}return curr1;} else {ListNode curr1 = loop1.next;while (curr1 != loop1) {if (curr1 == loop2) {return loop1;}curr1 = curr1.next;}}return null;
}/*** 找到链表的第一个入环节点，如果无环返回null。*/
public static ListNode getLoopNode(ListNode head) {if (head == null || head.next == null) {return null;}// slow and fast pointer go one stepListNode slow = head.next;ListNode fast = head.next.next;while (slow != fast) {// no_loopif (fast.next == null || fast.next.next == null) {return null;}slow = slow.next;fast = fast.next.next;}/*** find first into loop node*     1) slow go from intersect node, step equal 1*     2) fast become head, and go, stop equal 1, until fast = slow.*/fast = head;while (slow != fast) {slow = slow.next;fast = fast.next;}return slow;
}