圖解:?jiǎn)捂湵韯h除,不遍歷鏈表也能做(時(shí)間復(fù)雜度O(1))
在開(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)】