问：

给定两个可能有环也可能无环的单链表，头节点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;
}