题目

在本题中，单链表可能有环，也可能无环。
给定两个 单链表的头节点head1和head2，这两个链表可能相交，也可能不相交。
请实现一个函数，如果两个链表相交，请返回相交的第一个节点;
如果不相交，返回null即可。
要求:
如果链表1的长度为N，链表2的长度为M，时间复杂度请达到 O(N+M)，额外空间复杂度请达到O(1)

链表结构如下：

  public static class Node {
    public Node next;
    public int value;

    public Node(int data) {
      value = data;
    }
  }

思路

1、先判断两个链表有环，或者无环，有环则返回入环节点，否则为null

定理查找

若链表有两个指针，慢指针，一次跳1个节点，快指针一次跳2个节点，若链表成环。那么快节点一定会跟慢节点相遇。
相遇后，快节点回到头部，然后1个1个节点的走，直至和慢节点相遇，那么这时候相遇的节点就是要找的循环开始节点

算法实现

  public static Node getLoopNode(Node head) {
    // 小于2个节点的链表不可能组成环形
    if(head == null || head.next == null || head.next.next == null) {
      return null;
    }
    // 慢节点，一次跳1个节点
    Node n1 = head.next;
    // 快节点，一次跳2个节点
    Node n2 = head.next.next;
    // 定理：若链表成环，那么快节点一定会跟慢节点相遇
    while(n1 != n2) {
      if(n2.next == null || n2.next.next == null) {
        return null;
      }
      n2 = n2.next.next;
      n1 = n1.next;
    }
    // 相遇后，快节点回到头部，然后1个1个节点的走，直至和n1相遇
    // 那么这时候相遇的节点就是要找的循环开始节点
    n2 = head;
    while(n1 != n2) {
      n2 = n2.next;
      n1 = n1.next;
    }
    return n1;
  }

额外空间法-哈希表

若没有空间复杂度要求的话，这里的有无环判断，可以通过哈希表判断。链表开始从头遍历至末尾，先查表，若无则把Node放进表里，以Node为key，Node为值放入哈希表中。若从表中查到节点，那么第一个查到的节点就是入环节点。

算法实现

  public static Node getLoopNode2(Node head) {
    HashMap<Node, Node> map = new HashMap<Node, Node>();
    while(head != null) {
      if (map.get(head) != null ) {
        return head;
      }else {
        map.put(head, head);
      }
      head = head.next;
    }
    return null;
  }

2、分析两个链表列表有环，无环的情况

2.1、1个链表有环，1个链表无环

结论：永远不可能相交

2.2、两个链表都无环

若相交，那么必然如图所示：

两个无环链表相交情况

那么，针对以上结构，我们可以这样处理
1、判断哪个链表更长，把长链表从头节点开始一直指向下一个节点，直至与短链表长度一直
2、长短链表长度相等后，各种开始指向下一个节点，同时判断当前两个指针指向的节点是否相等，期间第一个相等的节点，即为第一个相交的节点。若遍历到结尾都不相等，则两个链表没有相交的节点。

算法实现

  public static Node noLoop1(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>0说明head1较长
    // 以下步骤是cur1指向较长的链表，cur2指向较短的链表
    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;
  }

若没有空间复杂度要求，我们可以使用HashMap来存储其中一个链表，另外一个链表遍历比较，实现如下：

  public static Node noLoop2(Node head1, Node head2) {
    HashMap<Node, Node> map = new HashMap<Node, Node>();
    while(head1 != null) {
      map.put(head1, head1);
      head1 = head1.next;
    }
    while(head2 != null) {
      if (map.get(head2) != null) {
        return head2;
      }
      head2 = head2.next;
    }
    return null;
  }

2.3、两个链表都有环

若两个链表有环且相交，只可能出现两种情况。

情况1

两个有环链表相遇情况1

如图所示，第一个相交结点必然不是环结点，而是入环前的节点。那么我们可以抹去成环部分，就可以转为两个无环链表的相交的问题了。

情况2

两个有环链表相遇情况2

如图所示，若是情况2，那么只需遍历L1的loop1，直至回到loop1，期间若与loop2相遇，那么两个链表的第一个相遇节点就是loop1或loop2。否则不相交

算法实现

  public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
    Node cur1 = null;
    Node cur2 = null;
    // 这时候两个链表构成的形状是 >-O
    // 这时候可以忽略环，转换为求两个无环链表的相交问题
    if (loop1 == loop2) {
      // 情况1
      cur1 = head1;
      cur2 = head2;
      int n = 0;
      // 只遍历到loop1
      while(cur1.next != loop1) {
        n++;
        cur1 = cur1.next;
      }
      // 只遍历到loop2
      while(cur2.next != 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 {
      //  情况2
      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 noLoop1(head1, head2);
    }
    if (loop1 != null && loop2 != null) {
      return bothLoop(head1, loop1, head2, loop2);
    }
    // 一个链表有环，一个链表无环，是不可能相交的
    return null;
  }

  /// 处理两个链表无环的情况
  /// 先把两个链表中，较长的链表走到跟较短的链表一样长
  /// 最后两个链表一起走，第一相遇的节点，就是第一个相交节点
  public static Node noLoop1(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>0说明head1较长
    // 以下步骤是cur1指向较长的链表，cur2指向较短的链表
    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;
  }

  /// 处理两个链表有环的情况
  public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
    Node cur1 = null;
    Node cur2 = null;
    // 这时候可以忽略环，转换为求两个无环链表的相交问题
    if (loop1 == loop2) {
      // 情况1
      cur1 = head1;
      cur2 = head2;
      int n = 0;
      // 只遍历到loop1
      while(cur1.next != loop1) {
        n++;
        cur1 = cur1.next;
      }
      // 只遍历到loop2
      while(cur2.next != 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 {
      // 情况2
      cur1 = loop1.next;
      while(cur1 != loop1) {
        if(cur1 == loop2) {
          return loop1;
        }
        cur1 = cur1.next;
      }
      return null;
    }
  }

  /// 获得环形链表的循环开始的节点
  public static Node getLoopNode(Node head) {
    // 小于2个节点的链表不可能组成环形
    if(head == null || head.next == null || head.next.next == null) {
      return null;
    }
    // 慢节点，一次跳1个节点
    Node n1 = head.next;
    // 快节点，一次跳2个节点
    Node n2 = head.next.next;
    // 定理：若链表成环，那么快节点一定会跟慢节点相遇
    while(n1 != n2) {
      if(n2.next == null || n2.next.next == null) {
        return null;
      }
      n2 = n2.next.next;
      n1 = n1.next;
    }
    // 相遇后，快节点回到头部，然后1个1个节点的走，直至和n1相遇
    // 那么这时候相遇的节点就是要找的循环开始节点
    n2 = head;
    while(n1 != n2) {
      n2 = n2.next;
      n1 = n1.next;
    }
    return n1;
  }