給定單向鏈表的頭指針和一個要刪除的節(jié)點的值，定義一個函數(shù)刪除該節(jié)點，返回刪除后的鏈表的頭節(jié)點。

示例

• 輸入: head = [4,5,1,9], val = 5

• 輸出: [4,1,9]

• 解釋: 給定你鏈表中值為 5 的第二個節(jié)點，那么在調(diào)用了你的函數(shù)之后，該鏈表應(yīng)變?yōu)?4 -> 1 -> 9.

說明

• 題目保證鏈表中節(jié)點的值互不相同

方法：雙指針

本題刪除值為 val 的節(jié)點分需為兩步：定位節(jié)點、修改引用。

• 定位節(jié)點： 遍歷鏈表，直到 head.val == val 時跳出，即可定位目標(biāo)節(jié)點。

• 修改引用： 設(shè)節(jié)點 cur 的前驅(qū)節(jié)點為 pre ，后繼節(jié)點為 cur.next ；則執(zhí)行 pre.next = cur.next ，即可實現(xiàn)刪除 cur 節(jié)點。

以示例說明，遍歷第一個節(jié)點 4 ，4 跟 val 值比對，發(fā)現(xiàn)不一致，繼續(xù)遍歷下一個節(jié)點，跟目標(biāo)值進(jìn)行比對，當(dāng)發(fā)現(xiàn)一致的時候，把上一個節(jié)點的 next 值指向當(dāng)前節(jié)點的下一個節(jié)點即可。

代碼如下：

復(fù)雜度分析

• 時間復(fù)雜度： O(N)，N 為鏈表長度，刪除操作平均需循環(huán) N/2 次，最差 N 次。

• 空間復(fù)雜度： O(1)，cur, pre 占用常數(shù)大小的額外空間。

END

本文內(nèi)容出處是力扣官網(wǎng)，希望和大家一起刷算法，在后面的路上不變禿但是變強！

好兄弟可以點贊并關(guān)注我的公眾號“javaAnswer”，全部都是干貨。