单向链表怎么能有两个头，找到它们的"common node"意味着什么？

Question

以下方法的javadoc包括:

问题中的单链表有两个头，n1和n2，它们在一个公共节点合并。返回n1和n2均可访问的第一个公共节点。这必须在O(n)时间内运行。

我不明白这段代码的目的。一个单链表怎么会有两个头呢?什么是公共列表(或公共节点)，为什么返回它?

有人可以提供输入列表或列表的一些示例，以及findCommonList方法返回后它或它们看起来像什么?

代码是:

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的代码，但我猜这是一个非常典型的单链表，引用了E类型的一些数据，并引用了下一个ListNode，称为next。最后一个ListNode将其next指向null。忽略对数据的引用，典型的列表看起来像这样:

lnA→lnB→lnC→…→lnZ→null

这种结构的一个(许多)问题是，没有一个列表"拥有"这些ListNode实例中的任何一个，所以多个列表可能会纠缠在一起:

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

findCommonList方法获取两个ListNode引用，n1和n2，并搜索它们有共同的第一个节点"向右"，这标志着它们共同尾部的开始。

n1和n2有什么共同的尾巴实际上取决于它们从哪里开始。把它们放在显眼的地方:

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

…将返回lnQ作为它们共同尾部的起点。(如果n2是从lnZ开始的，那么显然结果不可能包括lnQ——它不再在其中一个列表中，因此对它们都不常见。)

JavaDoc暗示这段代码只适用于类似于上面的情况，但它也处理一些相关的情况，这些情况最初可能看起来非常不同，比如当n1和n2指向相同列表的不同元素时:

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

甚至当他们指向两个不相关的列表时…由于所有列表都以对null的引用结束，因此两个"完全独立"的列表将返回null作为它们(零长度)公共尾部的开始:

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

findCommonList如何工作

findCommonList所做的第一件事是找出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"

这是我上面说的"搜索它们共有的第一个节点"的位。完成后，n1和n2都将指向同一个ListNode, lnQ，这将返回:

                    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循环将同步推进两个引用，直到它们到达两个列表共有的唯一"节点"，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将立即返回对ln3的引用，而不执行while的循环体。

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

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

…调整步骤什么也不做("advance 0 hops")，然后返回ln0，同样不执行while循环的体。