week8 作业

用户头像
雪涛公子
关注
发布于: 2020 年 07 月 29 日

1.

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;
}



用户头像

雪涛公子

关注

还未添加个人签名 2017.11.20 加入

还未添加个人简介

评论

发布
暂无评论
week8 作业