week8 作业

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

1,判断链表是否合并

两个单向链表,链表长度分别为m,n。这两个单向链表可能在某个元素处合并,如下图这样,也可能不合并。现给定两个链表的头指针,在不修改链表的情况下,如何快速的判断两个链表是否合并?如果合并,找到合并元素。





如果m,n长度不相等
较大的链表指针先往后移,直到两个链表剩下的元素个数相等为止。
此时两个链表的指针同时后移,并判断元素是否相等,如果相等,记录下相等元素(合并元素)
如果后面每个元素都相等,则两个链表有重合。

时间复杂度:O(m) 或 O(n) 较大链表的元素个数
空间复杂度:O(1)




用户头像

TiK

关注

还未添加个人签名 2018.04.26 加入

还未添加个人简介

评论

发布
暂无评论
week8 作业