链表相交的问题（java)

判断两个无环链表是否相交
首先我们要知道相交是什么概念

现在大家都知道了，两个链表相交，则两个链表共享一个尾部。
思路一：两个链表遍历到最后，看尾结点是不是一样的。

public boolean isIntersect(ListNode head1, ListNode head2){
    if(head1 == null || head2 == null){
        return false;
    }
    ListNode p1 = head1;
    ListNode p2 = head2;
    while(p1.next!=null){
        p1 = p1.next;
    }
    while(p2.next!=null){
        p2 = p2.next;
    }
    if(p1 == p2){
        return true;
    }
    return false;
}

public boolean isIntersect(ListNode head1, ListNode head2){
    if(head1 == null || head2 == null){
        return false;
    }
    ListNode p1 = head1;
    while(p1.next!=null){
        p1 = p1.next;
    }
    p1.next = head1;
    ListNode slow = head2;
    ListNode fast = head2;
    while(fast.next != null && fast.next.next != null){
        slow = slow.next;
        fast = fast.next.next;
        if(slow == fast){
            return true;
        }
    }
    return false;
}

如果相交，求第一个相交的点
对应上面的思路。
思路一：两个链表遍历到最后，看尾结点是不是一样的。尾结点一样代表相交。记下两个链表的长度（length1和length2）。然后重新开始，长链表结点先出发前进|length1-length2|步，再两个链表同时遍历。

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
    if(pHead1 == null || pHead2 == null){
        return null;
    }
    ListNode p1 = pHead1;
    ListNode p2 = pHead2;
    int length1 = 1;
    int length2 = 1;

    while(p1.next!=null){
        p1 = p1.next;
        length1++;
    }
    while(p2.next!=null){
        p2 = p2.next;
        length2++;
    }

    if(p1 != p2){
        return null;
    }

    p1 = pHead1;
    p2 = pHead2;

    if(length1 >= length2){
        for(int i = 0; i< length1 - length2; i++){
            p1 = p1.next;
        }
    }else{
        for(int i = 0; i< length2 - length1; i++){
            p2 = p2.next;
        }
    }

    while(p1 != null && p2 != null){ // 这里是p1,不是p1.next，因为可能只有最后一个结点相同
        if(p1 == p2){
            return p1;
        }
        p1 = p1.next;
        p2 = p2.next;
    }

    return null;
}

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
    if(pHead1 == null || pHead2 == null){
        return null;
    }
    ListNode p1 = pHead1;
    while(p1.next!=null){
        p1 = p1.next;
    }

    p1.next = pHead1;
    ListNode slow = pHead2;
    ListNode fast = pHead2;
    while(fast.next != null && fast.next.next != null){
        slow = slow.next;
        fast = fast.next.next;
        if(slow == fast){
            break;
        }
    }
    if(fast.next == null || fast.next.next == null){
        p1.next = null;
        return null;
    }
    ListNode pHead = pHead2;
    while(pHead!=slow){
        slow = slow.next;
        pHead = pHead.next;
    }
    p1.next = null;
    return slow;
}