C语言 查找两个相交链表的公共节点

Question

我在

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

例如

      ![Linked List example][1]

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

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

35->16->45

我回答他，我们可以在哈希图中存储一个链表的地址，并将第二个列表中的每个节点的地址与哈希图进行比较。通过这种方式，我们可以实现O(n(复杂性。但面试官并不满意。

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

Answer 1

如果

两个链表在某个节点相交，可以更好地监听，这样我们就可以遍历两个链表，找到每个列表的长度，然后将一个列表的指针向上移动到两个列表之间的距离，然后在你得到那个节点时同时移动两个指针，两个指针都是相等的。

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

   A. 遍历列表1并找到最后一个元素

   b. 遍历列表2并找到最后一个元素

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

在这里，我们只解析了一次列表：-(

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

   a. 创建一个变量(int( diff=0

   b. 解析列表 1 并增加每个节点的差异

   C. 解析列表 2 并减少每个节点的差异

   d. 如果 diff> 0 list1 更大，因此按差异时间推送 list1 的指针否则 list2 更大，所以按 mod(diff( 次推动 list2 的指针

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

Answer 2

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

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

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

Answer 3

我建议的解决方案：

你创建一个哈希图，迭代第一个列表，对于每个元素，您执行以下操作：hashMap.put({value}， "firstList"(;

在 O(n( 上，你会得到一个元素图。

迭代第二个列表，对于每个元素，请询问：hash_map.containsKey({number}( ？

如果是这样，交叉计数器 ++;

我认为最好的是O(N(。

这就是我要做的。