復(fù)習(xí)鏈表的插入

????鏈表的一個節(jié)點是由數(shù)據(jù)域和指針域構(gòu)成，指針域的地址值為下個元素的地址。那么我們需要插入或者刪除一個元素怎么處理呢？

• 先查看原始鏈表結(jié)構(gòu)，準(zhǔn)備將結(jié)點x插入鏈表中。

• 此時我們需要先保存n節(jié)點的地址(300)，n節(jié)點的地址存放在m節(jié)點的指針域，將此值賦值給x節(jié)點的指針域。(x->next=m->next)，變成了下圖所示。

• 此時再將m節(jié)點和x節(jié)點連接起來。m->next=x.如下圖所示。

看到這里，有些小伙伴可能會有疑問了。如果是空鏈表，這樣的插入方式就行不通的了呀(自己可以畫圖看看哈)，對，這就是要說的重點了，哨兵。

• 哨兵結(jié)點是什么？

我們可以先思考導(dǎo)致空鏈表不能使用第一種方案的原因，因為它沒有結(jié)點，我們自然無法獲取其地址，所以采用增加一個頭結(jié)點，那么此時空鏈表的結(jié)構(gòu)如下圖4，非空鏈表結(jié)構(gòu)如下圖5.

復(fù)習(xí)鏈表的刪除

• 上面簡單介紹了帶頭結(jié)點的鏈表，在刪除處理的時候同樣適用，所以我們以后就直接采用帶頭結(jié)點的鏈表講解。下面直接看看刪除節(jié)點圖。

1Leetcode237 刪除鏈表的節(jié)點

請編寫一個函數(shù)，使其可以刪除某個鏈表中給定的(非末尾)節(jié)點，你將只被給定要求被刪除的節(jié)點。

現(xiàn)有一個鏈表 -- head = [4,5,1,9]，它可以表示為:

示例1：

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

輸出: [4,1,9]

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

說明:

• 鏈表至少包含兩個節(jié)點。

• 鏈表中所有節(jié)點的值都是唯一的。

• 給定的節(jié)點為非末尾節(jié)點并且一定是鏈表中的一個有效節(jié)點。

• 不要從你的函數(shù)中返回任何結(jié)果。

先思考一分鐘喲！

效果更好哈！

01題目解析

• 常規(guī)套路

  • 找到待刪除結(jié)點的上一個結(jié)點的指針。

  • 將指針指向待刪除的下一個結(jié)點。如下圖7所示。

• 仔細看題

  • 發(fā)現(xiàn)沒，題目并沒有告訴我們其上一個結(jié)點，不要緊，我們可以想辦法構(gòu)造出一個結(jié)點，請看下。

  • 目標(biāo)還是刪除5，最后結(jié)果為[4,1,9]。我們把需要刪除的5結(jié)點的后面節(jié)點1賦值給它，如下圖8.

• 嘿嘿，現(xiàn)在兩個結(jié)點值1，不管刪除哪一個我們都能獲得結(jié)果，但是第二個節(jié)點1我們不方便刪除，但是第三個結(jié)點1還是輕松的。假設(shè)為p指針指向刪除的節(jié)點，那么直接就是p.next=p.next.next。如下圖9.

02代碼實現(xiàn)1c++版本

2python版本

3java版本

暖男告知

跟小藍每天進步一點點，生活就會美一點！

進入算法,面試學(xué)習(xí)群，一起成長！

關(guān)注下方，回復(fù)"進群"就進入我們小分隊。

關(guān)注就有內(nèi)部資源！

總結(jié)

以上是生活随笔為你收集整理的假设以带头结点的循环链表表示队列_[leetcode链表系列]2 删除链表中的节点的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。