检测两个链表是否合并

用户头像
行下一首歌
关注
发布于: 11 小时前

两个链表

有如下的两个链表1和2,检测链表有没有合并,如果有合并指出链表的值。

算法简述

合并到意思是两个链表当前指针的下一个节点的地址相同。那最直观的方法就是已最小表为基准表,遍历该基准表,并判断另一个表中是否有节点的指针指向基准表的当前节点,直到基准表遍历结束,这种方法的时间复杂度式O(n^2),准确的说应该是O(n * m)。

p = 链表1头指针;
q = 链表2头指针;
q = min{p,q}; // 选取最小链表
while(q.next != null){
while(p.next != null){
if(p.next == q){
return q.data;
}else{
p = p.next;
}
}
p = 链表1头指针;
q = q.next;
}
return 0;

分析

有没有更快的处理方式了呢?

改进

  1. 先遍历一遍最大的链表,并且组织一个Map<Node.next,Node.data>;

  2. 然后再遍历小的链表,并通过map查询是否存在Key即可,存在即说明有合并,不存在说明没有合并;

  3. 时间复杂度 = O(n)。

发布于: 11 小时前 阅读数: 3
用户头像

行下一首歌

关注

还未添加个人签名 2017.10.30 加入

半壁山房待明月,一盏清茗酬知音。

评论

发布
暂无评论
检测两个链表是否合并