找到 2 个双向链表的交集
find intersection of 2 doubly linked lists
我有一个作业需要找到 2 个单链接（单对单）列表的交集。我还必须为 2 个双向链接（双重 vs 双重）列表执行此操作：
对于单链表，我使用mergeSort()对两个列表进行排序，然后逐项比较==> O(m.log(m) + n.log(n))
我对双向链表感到困惑：同样可以工作，但我想可能有更快的方法。
有人可以告诉我是否有更有效的方法来找到 2 个双向链表的交集？我想也许我们可以合并它们并检查重复项，但我不确定这将如何工作以及效率如何。
编辑：注意这里的'intersection'是共享值，不是公共节点。
编辑：实施应该在不使用散列的情况下完成
如果其中一个列表非常短或比另一个短得多，则复杂度为 O(n*m) 的简单嵌套线性扫描可能比对较长的列表进行排序更快列表。这是非常小的 n 或 m（1 或 0）的最佳方法。
对于一般情况，您不能假设列表没有重复项，因此合并列表没有帮助。
使用散列 table:
查找 2 个列表的交集（单链接或双链接）或更一般地查找 2 个集合的交集可能是一种更快的方法
- 创建一个可以包含重复项的空哈希 table；
- 枚举第一个列表，在散列中插入每个元素table：O(n);
- 枚举第二个列表，对于每个元素，如果在哈希table中找到，则将其添加到交集并从哈希table中删除：O (米);
- 丢弃散列 table。
总时间复杂度是 O(n+m) 使用 O(n) 额外 space。一个额外的好处是列表不会用这种方法修改，这可能是一个要求。
我会详细说明我的评论。
假设两个 doubly-linked 列表相交。然后他们有一个共同的节点。根据该节点的指针确定两个方向上的所有节点，因此列表具有所有共同的节点。
对于cycle-free singly-linked列表，如果它们共享至少一个共同节点，那么沿着从该节点到末尾的指针确定所有后续节点。这意味着我们可以通过测量列表的长度找到公共节点，并使用两个指针比较从末尾开始 equi-distant 的节点，直到找到第一对相等的节点。这是 O(n) 时间和 O(1) space.
如果存在（或可能存在）循环，请使用 Floyd 的 cycle-finding 算法（也是 O(n) 时间和 O(1) space）找到它。这些列表共享共同的周期。如果初始节点不在循环中，则像以前一样进行（从循环开始 equi-distant）。
我有一个作业需要找到 2 个单链接（单对单）列表的交集。我还必须为 2 个双向链接（双重 vs 双重）列表执行此操作：
对于单链表，我使用
mergeSort()对两个列表进行排序，然后逐项比较==> O(m.log(m) + n.log(n))我对双向链表感到困惑：同样可以工作，但我想可能有更快的方法。
有人可以告诉我是否有更有效的方法来找到 2 个双向链表的交集？我想也许我们可以合并它们并检查重复项，但我不确定这将如何工作以及效率如何。
编辑：注意这里的'intersection'是共享值，不是公共节点。 编辑：实施应该在不使用散列的情况下完成
如果其中一个列表非常短或比另一个短得多，则复杂度为 O(n*m) 的简单嵌套线性扫描可能比对较长的列表进行排序更快列表。这是非常小的 n 或 m（1 或 0）的最佳方法。
对于一般情况，您不能假设列表没有重复项，因此合并列表没有帮助。
使用散列 table:
查找 2 个列表的交集（单链接或双链接）或更一般地查找 2 个集合的交集可能是一种更快的方法- 创建一个可以包含重复项的空哈希 table；
- 枚举第一个列表，在散列中插入每个元素table：O(n);
- 枚举第二个列表，对于每个元素，如果在哈希table中找到，则将其添加到交集并从哈希table中删除：O (米);
- 丢弃散列 table。
总时间复杂度是 O(n+m) 使用 O(n) 额外 space。一个额外的好处是列表不会用这种方法修改，这可能是一个要求。
我会详细说明我的评论。
假设两个 doubly-linked 列表相交。然后他们有一个共同的节点。根据该节点的指针确定两个方向上的所有节点，因此列表具有所有共同的节点。
对于cycle-free singly-linked列表，如果它们共享至少一个共同节点，那么沿着从该节点到末尾的指针确定所有后续节点。这意味着我们可以通过测量列表的长度找到公共节点，并使用两个指针比较从末尾开始 equi-distant 的节点，直到找到第一对相等的节点。这是 O(n) 时间和 O(1) space.
如果存在（或可能存在）循环，请使用 Floyd 的 cycle-finding 算法（也是 O(n) 时间和 O(1) space）找到它。这些列表共享共同的周期。如果初始节点不在循环中，则像以前一样进行（从循环开始 equi-distant）。