前言

以專題的形式更新刷題貼，歡迎跟我一起學習刷題，相信我，你的堅持，絕對會有意想不到的收獲。每道題會提供簡單的解答，如果你有更優雅的做法，歡迎提供指點，謝謝。

【題目描述】

給定鏈表的頭節點head，實現刪除鏈表的中間節點的函數。

例如：

步刪除任何節點；

1->2，刪除節點1；

1->2->3，刪除節點2；

1->2->3->4，刪除節點2；

1->2->3->4-5，刪除節點3；

【要求】

如果鏈表的長度為 N, 時間復雜度達到 O(N), 額外空間復雜度達到 O(1)

【難度】

士：★☆☆☆

【解答】

這道題要求刪除中間節點，我們可以采用雙指針的方法來做，就是用一個快指針和一個慢指針，快指針每次前進兩個節點，而慢指針每次前進一個節點。當快指針遍歷完節點時，慢指針剛好就在中間節點了。之前寫過一篇一些常用的算法技巧總結也有所過指針使用的一些技巧。

不過在做的時候，最好是先把一些特殊情況先處理好，例如刪除的可能是第一個節點，也有可能不用刪除節點(只有一個節點時就不用刪除了。

代碼如下public?static?Node?removeMidNode(Node?head)?{

if(head?==?null?||?head.next?==?null)

return?head;

if?(head.next.next?==?null)?{

return?head.next;

}

Node?fast?=?head.next.next;//快指針

Node?slow?=?head;//慢指針

//slow最終指向中間節點的前驅

while?(fast.next?!=?null?&&?fast.next.next?!=?null)?{

slow?=?slow.next;

fast?=?fast.next.next;

}

//進行刪除

slow.next?=?slow.next.next;

return?head;

}上次那道刪除倒數第 K 個節點的題(【鏈表問題】刪除單鏈表中的第K個節點) 其實也是可以使用雙指針的，但個人認為，那道題使用雙指針的方法并沒有我上次那個做法優雅，而這次刪除中間節點，則用雙指針比較優雅。至于原因，可以自己打下代碼看看。

之所以說這個事，是因為有人跟我題雙指針的建議，我是非常歡迎有人給我提建議的，不過你的建議如何。不過一上來就說我那篇文章太敷衍，我也是醉了。我開頭已經說了，只提供簡單的解答，而且也把刷題的文章放到次條了。

問題拓展

題目：刪除鏈表中 a / b 處的節點

【題目描述】

給定鏈表的頭節點 head、整數 a 和 b，實現刪除位于 a/b 處節點的函數。

例如：

鏈表：1->2->3->4->5，假設 a/b 的值為 r。

如果 r = 0，不刪除任何節點；

如果 r 在區間 (0,1/5] 上，刪除節點 1；

如果 r 在區間 (1/5,2/5] 上，刪除節點 2；

如果 r 在區間 (2/5,3/5] 上，刪除節點 3；

如果 r 在區間 (3/5,4/5] 上，刪除節點 4；

如果 r 在區間 (4/5,1] 上，刪除節點 5；

如果 r 大于 1，不刪除任何節點。

【要求】

如果鏈表的長度為 N, 時間復雜度達到 O(N), 額外空間復雜度達到 O(1)

【難度】

士：★☆☆☆

總結

以上是生活随笔為你收集整理的删除链表的中间节点 Java实现_【链表问题】删除单链表的中间节点的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。