如何判断两个链表是否相交？寻找相交的第一个节点

数据结构与算法

1.是否相交

这里还是有一点没有理解到，链表相交，。说是链表相交的话尾节点一定是一样的

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

2.寻找第一个相交节点

想办法使得遍历两个链表的时候进行同步。首先判断是否相交。然后判断较长的一个链表。截去前面多的不要，因为相交尾节点相同的话，前半部分多的是绝对不会相交的。

public int findFirstIntersect(ListNode head1, ListNode head2) {
        if (!isIntersect(head1, head2)) {
            return -1;
        }
        int len1 = length(head1);
        int len2 = length(head2);
        ListNode p;
        ListNode q;
        if (len1 > len2) {
            p = head1;
            q = head2;
        } else {
            p = head2;
            q = head1;
        }
        int k = Math.abs(len1 - len2);
        for (int i = 0; i < k; i++) {
            p = p.next;
        }
        while (p != null) {
            if (p == q) {
                break;
            } else {
                p = p.next;
                q = q.next;
            }
        }
        return p.val;
    }