架构师训练营第八周作业
1.链表相交
题目:直接leetcode上找到对应题目
https://leetcode-cn.com/problems/intersection-of-two-linked-lists-lcci/
解法:
解法1:哈希表 解法2:双指针
复杂度分析:
哈希表:时间复杂度O(m+n),m,n分别为两个链表长度 空间复杂度O(min(m+n))。
双指针:时间复杂度O(m+n),空间复杂度O(1)
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; }
哈希表:时间复杂度O(m+n),m,n分别为两个链表长度 空间复杂度O(min(m+n))。
双指针:时间复杂度O(m+n),空间复杂度O(1)
还未添加个人签名 2019.02.18 加入
还未添加个人简介
促进软件开发及相关领域知识与创新的传播
评论