前言:?

? ? ? ? 本文收錄于http://t.csdn.cn/n6UEP數(shù)據(jù)結(jié)構(gòu)刷題的博客中,首先歡迎大家的來訪，其次如有錯誤，非常歡迎大家的指正！我會及時更正錯誤！

目錄

一.鏈表的中間結(jié)點(diǎn)?

1.1原理:快慢指針的使用

鏈表元素個數(shù)為奇數(shù)時

鏈表元素個數(shù)為偶數(shù)時

1.2循環(huán)條件問題?

一.鏈表的中間結(jié)點(diǎn)?

來源:876. 鏈表的中間結(jié)點(diǎn) - 力扣（LeetCode）

題目:

1.1原理:快慢指針的使用

這個算法之所以有效，是因?yàn)?span style="color:#4da8ee;">fast指針的移動速度是slow指針的兩倍。

快慢指針的精妙之處在于,當(dāng)快指針移動到鏈表尾部時,慢指針就剛好移動了鏈表長度的一半,從而找到中間節(jié)點(diǎn)。因此當(dāng),fast指針到達(dá)鏈表尾部時，slow指針將正好指向鏈表的中間節(jié)點(diǎn)。無論鏈表長度奇偶,這個方法都可以在一次遍歷正確找到中間節(jié)點(diǎn)。

時間復(fù)雜度:O(n),因?yàn)橹槐闅v鏈表一次。
空間復(fù)雜度:O(1),因?yàn)闆]有使用額外的空間。

整體思路:

1. 函數(shù)以指向鏈表頭部的指針作為參數(shù)。

2. 初始化兩個指針?slow?和?fast，它們都指向鏈表的頭部。

3. 進(jìn)入一個循環(huán)，只要fast不為NULL且fast->next不為NULL，循環(huán)會繼續(xù)執(zhí)行。這個循環(huán)用于通過鏈表前進(jìn)指針。

4. 每次循環(huán)迭代中,slow?指針向前移動一步，通過賦值slow?= slow-> next。

5. fast指針向前移動兩步，通過賦值fast = fast?-> next -> next。

6. 當(dāng)循環(huán)結(jié)束時，slow?指針將指向鏈表的中間節(jié)點(diǎn)。這是因?yàn)?strong>fast指針的移動速度是slow指針的兩倍，當(dāng)?fast指針到達(dá)鏈表尾部時，slow指針剛好在鏈表的中間。

7. 最后，函數(shù)返回slow指針，即鏈表的中間節(jié)點(diǎn)。

鏈表元素個數(shù)為奇數(shù)時

動圖演示:

鏈表元素個數(shù)為偶數(shù)時

返回第二個中間結(jié)點(diǎn)的原因是題目要求:

?動圖演示:

1.2循環(huán)條件問題?

循環(huán)條件不能調(diào)換順序:

while 循環(huán)條件?fast && fast->next?不能寫成?fast->next && fast?的目的是為了確保在遍歷鏈表時不會出現(xiàn)空指針異常。

如果將循環(huán)條件調(diào)換為fast->next&& fast?，在鏈表長度為奇數(shù)時，當(dāng)快指針?fast指向最后一個節(jié)點(diǎn)時，fast->next仍然不為NULL，但此時fast已經(jīng)為NULL，這樣會導(dǎo)致在訪問fast的next指針時出現(xiàn)錯誤。

通過保持條件為fast && fast->next?，可以確保在fast 和 fast->next?每次迭代中，快指針都不為NULL，從而避免了空指針的訪問錯誤。這是正確處理快慢指針遍歷的關(guān)鍵。

因此，為了保證代碼的正確性，應(yīng)該保持原始代碼中的循環(huán)條件不變，即fast && fast->next。

代碼實(shí)現(xiàn)

struct ListNode* middleNode(struct ListNode* head){
      struct ListNode* slow=head,*fast=head;
      while(fast && fast->next)
      {
            slow=slow->next;
            fast=fast->next->next;
       }
       return slow;
}

代碼執(zhí)行:

? ? ? ? 本文到此結(jié)束，如有錯誤歡迎大家指正，感謝來訪！文章來源地址http://www.zghlxwxcb.cn/news/detail-634210.html

到了這里，關(guān)于【鏈表OJ 3】鏈表的中間結(jié)點(diǎn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！