单向链表怎么会有两个头，找到他们的"common node"是什么意思？

Question

以下方法的 JavaDocs 包括：

The singly linked list in the problem has two heads, n1 and n2, that merge at a common node. Return the first common node that is accessible from both n1 and n2. This must run in O(n) time.

我不明白这段代码的用途。单向链表怎么会有两个头？什么是公共列表（或公共节点），为什么返回？

有人可以提供一些输入列表的示例，以及在 findCommonList 方法 returns 之后它或它们的样子吗？

密码是：

public static<E> ListNode<E> findCommonList(ListNode<E> n1, ListNode<E> n2) {
int length1 = getLength(n1);
int length2 = getLength(n2);
if (length1 > length2)
    n1 = advance(n1, length1 - length2);
else
    n2 = advance(n2, length2 - length1);
while (n1 != n2) {
    n1 = n1.next;
    n2 = n2.next;
}
return n1; }

private static<E> ListNode<E> advance(ListNode<E> n, int k) {
while (k > 0) {
n = n.next;
k--; }
return n; 
}

private static<E> int getLength(ListNode<E> n) {
int total = 0;
while (n != null) {
    total++;
    n = n.next; }
return total;
}

Answer 1

我看不到 ListNode 的代码，但我猜这是一个非常典型的 single-linked 列表，引用了一些 E 类型的数据和参考下一个ListNode，叫做next。最后一个 ListNode 会将它的 next 指向 null。忽略对数据的引用，典型的列表如下所示：

lnA→lnB→lnC→…→lnZ→null

这种结构的（许多）问题之一是没有人列出 "owns" 这些 ListNode 个实例中的任何一个，因此多个列表可能会纠缠在一起：

ln0→ln1→ln2↘
            lnQ→lnR→…→lnZ→null
lnA→lnB→lnC↗

findCommonList 方法接受两个 ListNode 引用，n1 和 n2，然后搜索它们共有的第一个节点 "to the right" , 这标志着它们共同尾巴的开始。

n1 和 n2 的共同尾巴实际上取决于它们的起点。把它们放在明显的地方：

n1
↓
ln0→ln1→ln2↘
            lnQ→lnR→…→lnZ→null
lnA→lnB→lnC↗
↑
n2

...将 return lnQ 作为他们共同尾巴的开始。（如果 n2 而是从 lnZ 开始，那么显然结果不会包含 lnQ --- 它不再在其中一个列表中，因此它们对它们都不常见.)

JavaDoc 暗示此代码仅适用于上述情况，但它也处理了一些乍一看可能非常不同的相关情况，例如 n1 和 n2指向 same 列表的不同元素：

n1
↓
ln0→ln1→ln2→ln3→ln4→…→null
            ↑
            n2

甚至当它们指向两个不相关的列表时... 由于所有列表都以对 null 的引用结尾，因此两个 "completely independent" 列表将 return null 作为其 (zero-length) 公共尾部的开始：

n1
↓
ln0→ln1→ln2→ln3→ln4↘
                    null
        lnA→lnB→lnC↗
        ↑
        n2

findCommonList 的工作原理

findCommonList 做的第一件事是找出 "far" n1 和 n2 是如何从它们各自列表的末尾开始的（有多少元素从 null).

在此示例中，n1 比 n2“远 2”：

n1
↓
ln0→ln1→ln2→ln3→ln4↘
                    lnQ→…→lnZ→null
        lnA→lnB→lnC↗
        ↑
        n2

然后，它使两个参考中更远的一个前进，使其与 null 的距离与另一个相同。它跳过的元素不可能是公共尾部的一部分，因为公共尾部不可能比输入列表之一长。

前进后n1:

        n1
        ↓
ln0→ln1→ln2→ln3→ln4↘
                    lnQ→…→lnZ→null
        lnA→lnB→lnC↗
        ↑
        n2

现在我们进入了 while 循环，它可以改写为：

START:
if n1 and n2 point to the same ListNode:
    return that ListNode
otherwise:
    advance n1 and n2 each one hop to the right
go back to "START"

这就是我上面说的位"goes searching for the first node 'to the right' that they have in common"。完成后，n1 和 n2 将指向相同的 ListNode、lnQ，这将是 returned:

                    n1
                    ↓
ln0→ln1→ln2→ln3→ln4↘
                    lnQ→…→lnZ→null
        lnA→lnB→lnC↗
                    ↑
                    n2

请注意，这也适用于我上面概述的其他情况。

如果n1和n2引用两个完全独立的列表：

n1
↓
ln0→ln1→ln2→ln3→ln4↘
                    null
        lnA→lnB→lnC↗
        ↑
        n2

首先，更远的参考会前进：

        n1
        ↓
ln0→ln1→ln2→ln3→ln4↘
                    null
        lnA→lnB→lnC↗
        ↑
        n2

然后 while 循环将同步推进两个引用，直到它们到达两个列表唯一的 "node" 共同点，null:

                    n1
                    ↓
ln0→ln1→ln2→ln3→ln4↘
                    null
        lnA→lnB→lnC↗
                    ↑
                    n2

如果n1和n2已经指向同一个列表，那就更简单了：

n1
↓
ln0→ln1→ln2→ln3→ln4→…→null
            ↑
            n2

findCommonList 将从推进远参考开始，与之前相同：

            n1
            ↓
ln0→ln1→ln2→ln3→ln4→…→null
            ↑
            n2

...已经完成了！ findCommonList 将立即 return 引用 ln3，而不会执行 while 循环的主体。

最后，如果n1和n2开始指向相同ListNode:

n1
↓
ln0→ln1→ln2→ln3→ln4→…→null
↑
n2

...调整步骤不执行任何操作 ("advance 0 hops")，然后 ln0 被 returned，再次不执行 while 循环的主体。

单向链表怎么会有两个头，找到他们的"common node"是什么意思？

How can a singly-linked list have two heads, and what does it mean to find their "common node"?

java

singly-linked-list