编程判断两个链表是否相交.pdf
《编程判断两个链表是否相交.pdf》由会员分享,可在线阅读,更多相关《编程判断两个链表是否相交.pdf(3页珍藏版)》请在文库网上搜索。
1、写书评,赢取编程之美-微软技术面试心得 编程判断两个链表是否相交 给出两个单向链表的头指针(如图 3-8 所示),比如h 1 、h 2 ,判断这两个链表是否 相交。这里为了简化问题,我们假设两个链表均不带环。 图3-8 链表相交示意图 写书评,赢取编程之美-微软技术面试心得 分析与解法 这样的一个问题, 也许我们平时很少考虑。 但在一个大的系统中, 如果出现两个链表相 交的情况, 而且释放了其中一个链表的所有节点, 那样就会造成信息的丢失, 并且另一个与 之相交的链表也会受到影响, 这是我们不希望看到的。 在特殊的情况下, 的确需要出现相交 的两个链表,我们希望在释放一个链表之前知道是否有其他
2、链表跟当前这个链表相交。 【解法 一】 直观的想法 看到这个问题,我们的第一个想法估计都是,“不管三七二十一”,先判断第一个链表 的每个节点是否在第二个链表中。这种方法的时间复杂度为O(Length(h 1 ) * Length(h 2 )。可 见,这种方法很耗时间。 【解法 二】 利用 计数 的 方法 很容易想到, 如果两个链表相交, 那么这两个链表就会有共同的节点。 而节点地址又是 节点的唯一标识。 所以, 如果我们能够判断两个链表中是否存在地址一致的节点, 就可以知 道这两个链表是否相交。一个简单的做法是对第一个链表的节点地址进行 hash 排序,建立 hash 表,然后针对第二个链表的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编程 判断 两个 是否 相交