LeetCode160-两个链表的交集

Question

这是LeetCode网页上第一个两个链表相交的例子。 第一个链表 A 是 [4,1,8,4,5]，第二个链表 B 是 [5,6,1,8,4,5]。我发现两个链表的交集部分是[1,8,4,5]。但官方的解释是“相交节点的值为8，从A的头部开始读为[4,1,8,4,5]。从B的头部开始读为[5,6,1, 8,4,5].A中相交节点之前有2个节点；B中相交节点之前有3个节点。 谁能解释一下为什么在这种情况下路口的起始节点是“8”而不是“1”？ 非常感谢！

Answer 1

该图像提供了重要的上下文（取自https://leetcode.com/problems/intersection-of-two-linked-lists/）：

您正在寻找两个列表开始相交的点 - 这取决于节点连接，而不是它们的值。 A 和 B 中的“1”并不意味着它们相交，如图所示。

Answer 2

我之前也有同样的疑问，问题是我试图比较节点的值，假设节点A的值为1，另一个节点B的值为1，问题是如果我们只比较节点它们的值我们忽略了节点的其他因素，如它的地址、节点中的其他下一个元素、它的长度等。因此，我们必须在节点的所有方面进行匹配，而不是按照 nodeA.val == nodeB.val 进行匹配即节点A == 节点B。如下图：

while node1_to_use is not None and node2_to_use is not None:
    if node1_to_use == node2_to_use:   # ignore doing this node1_to_use.val == node2_to_use.val           
        return node2_to_use      

    node1_to_use = node1_to_use.next
    node2_to_use = node2_to_use.next 

Answer 3

发生这种情况是因为

A

和

B

中值为 1 的节点（

A

中的第二个节点和

B

中的第三个节点）是 不同的节点引用。参见：

虽然看起来

A[1]

和

B[2]

具有相同的值，但它们指向内存中的两个不同位置。参见：

在这个新图像中，考虑节点值下方的内容作为其在内存中的位置的表示。请注意内存位置如何仅从值为 8的节点开始对齐。