在開(kāi)始這個(gè)問(wèn)題之前，先想想，如果給定單鏈表中的某個(gè)結(jié)點(diǎn)，如何在單鏈表中刪除該節(jié)點(diǎn)?

對(duì)于一個(gè)單鏈表，它每個(gè)結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)除了存儲(chǔ)自身的數(shù)據(jù)之外，還需要記錄鏈表上，下一個(gè)結(jié)點(diǎn)的地址，通常我們將這個(gè)地址稱(chēng)之為后續(xù)指針 next。

那如上圖所示，我想刪除其中的 C 結(jié)點(diǎn)，需要做什么操作?很簡(jiǎn)單，將 B 結(jié)點(diǎn)的后續(xù)指針 next 指向 D 結(jié)點(diǎn)即可。

此處應(yīng)該清晰了，要?jiǎng)h除鏈表上的某個(gè)結(jié)點(diǎn)，我們需要知道三個(gè)結(jié)點(diǎn)：

• 待刪除的結(jié)點(diǎn)。
• 待刪除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。
• 待刪除結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)。

思路：實(shí)際刪除下一個(gè)結(jié)點(diǎn)

再來(lái)回顧最開(kāi)始的問(wèn)題，當(dāng)我們已知某個(gè)結(jié)點(diǎn)的時(shí)候，它的后續(xù)結(jié)點(diǎn)我們也是知道的。唯一的問(wèn)題，就是他的前驅(qū)結(jié)點(diǎn)我們不知道。

最簡(jiǎn)單的解決方法，就是將鏈表遍歷一遍，獲得待刪除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，對(duì)其進(jìn)行操作。

當(dāng)涉及到遍歷鏈表的時(shí)候，時(shí)間復(fù)雜度妥妥的變成 O(n)，這就與題不符了。

而問(wèn)題主要卡在了，我們?nèi)绾沃来齽h除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。試著換一個(gè)思路想想，我們只需要?jiǎng)h除該結(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)，而并不是刪除該結(jié)點(diǎn)對(duì)應(yīng)地址中的內(nèi)容。

那么就可以將待刪除結(jié)點(diǎn)的數(shù)據(jù)，和它的后續(xù)結(jié)點(diǎn)的數(shù)據(jù)進(jìn)行互換，然后對(duì)它的后續(xù)結(jié)點(diǎn)進(jìn)行刪除操作，以此來(lái)達(dá)到 O(1) 時(shí)間復(fù)雜度的單鏈表刪除。

問(wèn)題：待刪除節(jié)點(diǎn)是***一個(gè)節(jié)點(diǎn)

這個(gè)思路還存在一個(gè)問(wèn)題，我們實(shí)際刪除的是待刪除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)。還記得前面說(shuō)，刪除單鏈表中的某個(gè)結(jié)點(diǎn)，實(shí)際上是需要知道三個(gè)結(jié)點(diǎn)的。

那么，如果刪除的結(jié)點(diǎn)，是單鏈表的***一個(gè)結(jié)點(diǎn)，怎么辦?

這時(shí)我們?nèi)匀恍枰獜逆湵淼念^結(jié)點(diǎn)開(kāi)始遍歷，得到待刪除節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，并完成刪除操作，時(shí)間復(fù)雜度恢復(fù)到 O(n)。

而題目要求我們需要在 O(1) 的時(shí)間復(fù)雜度內(nèi)完成刪除操作，這樣是不是不符合題目要求呢?

其實(shí)不然，假設(shè)單鏈表總共有 n 個(gè)節(jié)點(diǎn)，這種算法在 n-1 的情況下時(shí)間復(fù)雜度都是 O(1)，只有在待刪除結(jié)點(diǎn)為單鏈表的***一個(gè)結(jié)點(diǎn)時(shí)，時(shí)間復(fù)雜度才會(huì)恢復(fù)到 O(n)，那么平均時(shí)間復(fù)雜度 [(n-1)*O(1)+O(n)]/n，計(jì)算下來(lái)仍然為 O(1)。

【本文為51CTO專(zhuān)欄作者“張旸”的原創(chuàng)稿件，轉(zhuǎn)載請(qǐng)通過(guò)微信公眾號(hào)聯(lián)系作者獲取授權(quán)】

戳這里，看該作者更多好文