單鏈表的中間節點

-3

我發現這個代碼打印C++中的一個列表的中間節點，但我不明白代碼...有人可以解釋我呢？單鏈表的中間節點

Type& findMiddleNode() 
{ 
    int check = 0; 
    nodeType *current; 
    nodeType *mid; 

    current = first; 
    mid = first; 

    while (current != NULL) 
    { 
     current = current->link; 
     check = (check + 1) % 2; 

     if (check == 0) 
      mid = mid->link; 
    } 

    return mid->info; 
}

PD：此代碼工作完美，但我不明白！有人幫助我理解這一點。謝謝！

來源

2016-07-26 Jhonny Afonso

你不完全明白什麼？如果你這麼說，我們可以給予更好的幫助:) – Rakete1111

這個想法是有兩個指針以不同的速度遍歷列表，其速度是另一個速度的兩倍。快速指針在每次迭代時都會被提前，而慢速指針則只會在每次迭代中進行。當快速指針到達列表的末尾時，慢速指針恰好在中間。 –

我不明白指針電流和中間的功能，以及無功電流。我不明白在while循環中的過程 –

的基本思想是通過在列表中移動兩個指針B和A，但爲B移動在只有一半A.

聲明

check = (check + 1) % 2;

＆hellip的速度;給出check的值爲0,1,0,1等等，它僅用於每移動一次A才移動B.

對於檢查單向鏈表是否包含循環的問題，同樣的想法是一個可能的（和預期的）答案。在這種情況下，快速移動的指針會在進入循環後跟上緩慢的指針。

更簡單的方法做同樣的，只有關於由節目花費同樣的工作，是（1）計算節點ñ的數量，和（2）在開始再次開始，去節點號n/2。

工序（1）移動的指針Ñ倍，像上述A，和步驟（2）移動的指針Ñ/2倍，如乙上方。

來源

2016-07-26 04:22:41

單鏈表的中間節點

回答

相關問題