如何找到两个单链表的公共节点点？
如何找到两个单链表的公共节点点？
提问于 2020-07-11 08:31:22
我解决这个问题的方法是使用hashmap来存储第一个链接列表的地址，遍历第二个数组，并检查我是否找到了这个地址，发现我会在那个地址返回节点。这需要O(m+n)，其中m和n是链表的长度，但这里我们使用O(线性)空间复杂度。我找到了另一种解决这个问题的方法，它有固定的空间，但同时也很复杂，但它并没有消除我的疑虑。link to the question
如果我的输入是
list 11 = 1 -> 2 -> 3 -> 4 -> 6 ->7;
list l2 = 2 -> 9;在这种情况下，在截断额外的长度之后，我对列表的一次遍历会变成这样
diff=4; // i would advance the list 1 by 4 elements as it has greater length
l1= 6-> 7;
l2= 2 -> 9;这里我失去了我的交叉口节点。有人能帮我吗？
回答 1
Stack Overflow用户
回答已采纳
发布于 2020-07-11 08:50:15
只有当输入链接列表与交点相同时，该方法才有效，如下所示：
1 -> 2 -> 3 -> 4 -> 5
12 -> 11-> 10 -> 3 -> 4 -> 5在这里，这两个列表与交点3是相同的。
只有这样，该算法才能工作。
注意：
这个问题基本上是给出了一个倒Y形列表(两个列表组合)的交点的求取问题。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/62846935
复制相关文章
相似问题
腾讯云开发者
