第八周作业
1.两个单向链表(链表长度分别为 m,n),这两个链表有可能在某个元素合并,也可能不合并。现在给定两个链表的头指针,在不修改链表的情况下,如何快速的判断两个链表是否合并?如果合并,找到合并的元素。
请用(伪)代码描述算法,并给出时间复杂度和空间复杂度
分别循环两个链表,
List<Object> a
List<Object> b
Object lastElementA = a.get(a.getSize() - 1);
Object lastElementB = b.get(b.getSize() - 1);
如果有合并,那么最后一个元素必定相同,所以 lastElementA == lastElementB 为 true,否则没有合并。
取合并元素,比较两个链表的长度,a.getSize() - b.getSize() =c,再让较长的链表先循环 c 个元素,此时两个链表长度一致。再同时开始循环,比较第一个相同的节点
时间复杂度是 O(A+B),空间复杂度是 O(n)
评论 (1 条评论)