从两个相交的链表中查找相交节点

Question

假设有两个单链表,它们在某个点相交并成为单个链表.

两个列表的头部或起始指针都是已知的,但交叉节点是未知的.此外,列表中每个列表中的节点数量在它们相交之前是未知的,并且两个列表可能具有不同,即List1在到达交叉点之前可能有n个节点,并且List2可能在到达交点之前有m个节点,其中m和n可以是

• m = n,
• m <n或
• m> n

一种已知或简单的解决方案是将第一列表中的每个节点指针与第二列表中的每个其他节点指针进行比较,匹配节点指针将通过该指针引导我们到交叉节点.但是,在这种情况下,时间复杂度将是O(n ²),这将是很高的.

找到交叉节点的最有效方法是什么？

Answer 1

这需要O(M + N)时间和O(1)空间,其中M和N是链表的总长度.如果公共部分很长(即M,N >> m,n)可能效率低下

1. 遍历两个链表以找到M和N.
2. 回到头部,然后遍历| M - N | 较长列表上的节点.
3. 现在进入锁定步骤并比较节点,直到找到常见节点.

编辑:请参阅http://richardhartersworld.com/cri/2008/linkedlist.html

Answer 2

如果可能,您可以添加"颜色"字段或类似于节点.迭代其中一个列表,随时为节点着色.然后迭代第二个列表.一旦到达已经着色的节点,就会找到交叉点.

Answer 3

将两个列表的内容(或地址)转储到一个哈希表中.第一次碰撞是你的交集.