如何判斷兩個無環連結清單是否相交

問題

​ 如何判斷兩個無環連結清單是否相交，相交則傳回第一個相交節點，不相交傳回null。

思路

​ 如果兩個無環連結清單相交，那麼從相交節點開始，一直到兩個連結清單終止的這段，二者共享。具體如下：

​ 1.連結清單1從頭節點開始，走到最後一個節點，統計連結清單1的長度記為len1，同時記錄連結清單1的最後一個節點記為end1。

​ 2.連結清單2從頭節點開始，走到最後一個節點，統計連結清單2的長度記為len2，同時記錄連結清單2的最後一個節點記為end2。

​ 3.如果end1 != end2，說明二者不相交，傳回null。否則，進入步驟4。

​ 4.如果連結清單1比較長，連結清單1就先走len1-len2步；如果連結清單2比較長，連結清單2先走len2-len1步。然後兩者一起走。走的過程中，兩個連結清單第一次走到一起的那個節點，就是第一個相交的節點。

代碼

public Node noLoop(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;
    }
    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;
}