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

Question

关闭。这个问题需要更多 focused .它目前不接受答案。












想改进这个问题？更新问题，使其仅关注一个问题 editing this post .

6年前关闭。




Improve this 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 之后的样子吗？方法返回？

代码是:

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作为它们(零长度)公共(public)尾部的开始:

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 的距离相同。作为另一个。它跳过的元素不可能是公共(public)尾部的一部分，因为公共(public)尾部不可能比输入列表之一长。

前进后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

...调整步骤什么都不做(“提前 0 跳”)，然后 ln0返回，再次不执行 while 的主体环形。