如何判断两个链表是否相交 - 高飞网
27 人阅读

如何判断两个链表是否相交

2016-12-16 17:13:45

有两个单身链表,假设他们没有环,如何判断两个链表是否相交?

如何判断两个链表是否相交

思路

    根据单链表的定义,每个结点最多只有一个后继结点,可能没有后继结点(如尾结点)。因此,如果两个单链表相交,那么只有可能是下面的第三个情况:

    即,如果两个链表相交,自它们相交开始,后面的结点完全重合,有相同的尾结点。


    因此,只要尾结点相同,就能断定这两个链表相交。

代码实现


public static boolean isIntersect(LinkList l1, LinkList l2) {
        Node head1 = l1.head;
        Node head2 = l2.head;
        Node tail1 = head1;
        Node tail2 = head2;
        while (tail1.next != null) {
            tail1 = tail1.next;
        }
        while (tail2.next != null) {
            tail2 = tail2.next;
        }
        return tail1 == tail2;
    }

两个链表相交,如何得到相交点

思路

    如果两个链表长度相同,那么让两个指针分别指向头结点,以相同的速度往前走,则肯定会在相交点相遇。如果两个链表长度不同,可以让指向长的链表的指针往前移动一端距离,使剩下的到尾结点的距离相同,那移多少呢?很显示,计算一下两个链表的长度,L1和L2,L1与L2的差的绝对值即为移动的长度,0的时候不用移动。

代码实现


public static Node interPoint(LinkList l1, LinkList l2) {
        int len1 = l1.size();
        int len2 = l2.size();
        Node p1 = l1.head;
        Node p2 = l2.head;
        if (len1 > len2) {
            for (int i = 0; i < (len1 - len2); i++) {
                p1 = p1.next;
            }
        } else {
            for (int i = 0; i < (len2 - len1); i++) {
                p2 = p2.next;
            }
        }
        while (p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }



还没有评论!
23.22.61.134