LeetCode算法题-Intersection of Two Linked Lists(Java实现)

LeetCode算法题-Intersection of Two Linked Lists(Java实现)

这是悦乐书的第178次更新,第180篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第37题(顺位题号是160)。编写程序以找到两个单链表交叉的节点。例如:

以下两个链表:

A:       a1→a2
                           ↘
                                c1→c2→c3
                           ↗
B:b1→b2→b3

链表A和链表B在c1处相交。

注意

如果两个链接列表根本没有交集,则返回null。

函数返回后,链接列表必须保留其原始结构。

可以假设整个链接结构中没有任何环。

代码最好在O(n)时间内运行,并且只使用O(1)内存。

本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。

02 第一种解法

这两个单链表,也可以看做是两数组,找出其中重复元素开始位置的值,最直接的办法就是上两层循环,外层遍历链表A,内层循环遍历链表B,直到遇到相交的节点为止,否则返回空。

特殊情况:当两链表中有一个为空的话,直接返回空。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) {
        return null;
    }
    ListNode B = headB;
    while (headA != null) {
        while (headB != null) {
            if (headA == headB) {
                return headA;
            }
            headB = headB.next;
        }
        headA = headA.next;
        headB = B;
    }
    return null;
}

但是此种解法的时间时间复杂度是O(n^2),最坏的情况是两链表的长度都是n,并且相交的节点在最后位置或者没有相交的点。

03 第二种解法

先来看个例子,假设A和B两人要比武,A的功夫等级是10级,B的功夫等级是8级,B觉得这样比武不公平,就让A把实力压制到8级,再去和B比武,此时两人的功夫等级都是8级,于是开始了一场惊天动地的比武…

回到此题中来,因为无法确定两个链表的长度是否相等,就算两者有交点,但是起点不一样,还是会错过,无法找到交点。这时,我们就需要判断两链表的长度,重新定义好起点,才能开始遍历节点。

如果链表A长度大于链表B的长度,此时链表A就需要先向前移动两者之间长度差值个节点,然后才能和B开始依次遍历比较,反之B也是如此。

public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
    int len1 = findLength(headA);
    int len2 = findLength(headB);
    int diff = (len1 >= len2) ? (len1 - len2) : (len2 - len1);
    if (len1 >= len2) {
        while (diff > 0) {
            headA = headA.next;
            diff--;
        }
    } else {
        while (diff > 0) {
            headB = headB.next;
            diff--;
        }
    }
    while (headA != null || headB != null) {
        if (headA == headB) {
            return headA;
        }
        headA = headA.next;
        headB = headB.next;
    }
    return null;
}

public int findLength(ListNode head) {
    int len = 0;
    while (head != null) {
        len += 1;
        head = head.next;
    }
    return len;
}


04 第三种解法

还记得之前那道判断单链表是否有环的题目吗?没错,此题我们也可以借助环的思路来解题。

当遍历A链表时,如果遍历到了最后一位节点,此时跳转到B链表的起始节点,然后开始遍历B链表;当遍历B链表时,如果遍历到了最后一位节点,此时跳转到A链表的起始节点,然后开始遍历A链表。此时就相当于在遍历一条由链表A和链表B组合起来的新链表,如果此新链表存在环,那么表示两链表是有交点的,如果遍历完都没有碰到环,说明两链表是没有交点的。

public ListNode getIntersectionNode3(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) {
        return null;
    }
    ListNode A = headA;
    ListNode B = headB;
    while (A != B) {
        if (A != null) {
            A = A.next;
        } else {
            A = headB;
        }
        if (B != null) {
            B = B.next;
        } else {
            B = headA;
        }
    }
    return A;
}


05 小结

此题最优解法是第三种解法,其次是第二种,最差的解法是第一种。

算法专题目前已连续日更超过一个月,算法题文章37+篇,