單鏈表如何能有兩個頭，找到他們的「共同節點」意味着什麼？下面

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爲「2更遠」比n2：

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 

...的調整步驟不執行任何操作（ 「前進0跳」），然後返回ln0，無需再次執行循環體while。