c - 查找两个相交链表的公共(public)节点

Question

我在面试中被问到，如果我们有两个链表，它们在多个节点上相交，那么我们如何找到链表相交的公共(public)节点。还要找到复杂性最小的解决方案。

例如

      ![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) 的复杂度。但面试官并不满意。

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

Answer 1

可以通过更好的方式实现监听两个链表是否在某个节点相交，这样我们就可以遍历两个列表找到每个列表的长度然后将一个列表的指针移动到两个列表之间的距离然后移动每当你获得该节点时，两个指针都会同时指向他的方向，两个指针都相等......

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

   a.遍历list1并找到最后一个元素

   b.遍历list2并找到最后一个元素

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

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

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

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

b.解析 list1 并为每个节点增加 diff

c.解析 list2 并减少每个节点的 diff

d.如果 diff > 0 list1 更大，则将 list1 的指针插入 diff 次否则list2更大，所以将list2的指针插入mod(diff)次

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