架构师训练营第八周作业

用户头像
Geek_2dfa9a
关注
发布于: 2020 年 07 月 29 日

1.链表相交

题目:直接leetcode上找到对应题目

https://leetcode-cn.com/problems/intersection-of-two-linked-lists-lcci/

解法:

解法1:哈希表 解法2:双指针

public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode curA = headA;
ListNode curB = headB;
while (curA != curB) {
if (curA == null) {
curA = headB;
} else {
curA = curA.next;
}
if (curB == null) {
curB = headA;
} else {
curB = curB.next;
}
}
return curA;
}



复杂度分析:

  1. 哈希表:时间复杂度O(m+n),m,n分别为两个链表长度 空间复杂度O(min(m+n))。

  2. 双指针:时间复杂度O(m+n),空间复杂度O(1)

用户头像

Geek_2dfa9a

关注

还未添加个人签名 2019.02.18 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营第八周作业