week8 作业

关注

发布于: 2020 年 07 月 29 日

1) 借用缓存，时间复杂度 O(m + n)，空间复杂度 O(m)；

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {        if (headA == null || headB == null) return null;
        Set<ListNode> set = new HashSet<ListNode>();        ListNode curr = headA;        while (curr != null) {            set.add(curr);            curr = curr.next;        }
        curr = headB;        while (curr != null) {            if (set.contains(curr)) return curr;            curr = curr.next;        }        return null;    }

复制代码

2) 双指针法，时间复杂度 O(m + n)，空间复杂度 O(1)；

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

复制代码

发布于: 2020 年 07 月 29 日阅读数: 63

雪涛公子

关注

还未添加个人签名 2017.11.20 加入

还未添加个人简介

发布

暂无评论

创作场景

week8 作业

雪涛公子

评论