0

我在采访中被问到，如果我们有两个链表相交于一个以上的节点，那么我们如何找到链表相交的公共节点。还要找到复杂度最低的解决方案。

例如 

      ![Linked List example][1]

链表 1 = 11->12->13->14->15->16->17->54

链表 2 = 23->24->13->26->14->15->35->16->45

我回答他说，我们可以将一个链表的地址存储在 hashmap 中，并将第二个链表中每个节点的地址与 hashmap 进行比较。这样我们就可以实现 O(n) 复杂度。但面试官并不满意。

请提出任何更好的解决方案。提前致谢。

4

2 回答 2

1

如果两个链表在某个节点处相交，则可以以更好的方式实现监听，这样我们就可以遍历两个链表找到每个链表的长度，然后将一个链表的指针移动到两个链表之间的距离，然后移动两个指针每当你得到那个节点时，同时进入他的方式，两个指针都相等..

  1. 给定两个单链表，判断它们是否相交。在单次迭代中执行此操作。

    一个。遍历list1，找到最后一个元素

    湾。遍历list2并找到最后一个元素

    C。检查 list1 的最后一个元素是否 == list2 的最后一个元素，如果相等，则相交否则不

在这里，我们只解析了一次列表:-)

  1. 还要在 O(n) 时间和 O(1) 空间中找到相交节点，他们要求在 O(1) 空间中进行操作，因此我们只需要使用一个变量 :-)

    一个。创建一个变量(int) diff=0

    湾。解析 list1 并为每个节点增加 diff

    C。解析list2并减少每个节点的差异

    d。如果 diff > 0 list1 较大，则将 list1 的指针推入 diff 次，否则 list2 较大，则将 list2 的指针推入 mod(diff) 次

    e. 现在检查两个指针​​是否相等，直到我们到达结束

于 2013-10-23T17:25:33.147 回答
0

如果值是整数并且您有无限的内存，您可以执行以下操作：

  1. 遍历每个列表一次，找到全局最大值MAX
  2. 分配一个布尔数组A，大小为MAX
  3. X遍历一个列表，对于列表集中的每个值A[X] = true
  4. 遍历第二个列表，对于列表中的每个值Y，如果A[Y] = truethenY是列表交集

这运行 O(N) 时间（我相信你不能做得更好，因为列表没有排序）

于 2013-10-06T19:22:30.743 回答