1. 刪除單鏈表中的所有的指定結(jié)點(diǎn)

1.1 刪除思路

• 定義一個(gè) cur 來代替 head 遍歷單鏈表。
• 遇到指定結(jié)點(diǎn)就開始刪除。
• 是不是要?jiǎng)h除的結(jié)點(diǎn)， cur 都指向下一個(gè)結(jié)點(diǎn)，直到表遍歷完成。
• 單鏈表中可能沒有要?jiǎng)h除的結(jié)點(diǎn)。
• 定義一個(gè) prev 指向要?jiǎng)h除結(jié)點(diǎn)的前驅(qū)。
• 如果單鏈表的第一個(gè)結(jié)點(diǎn)就是要?jiǎng)h除的結(jié)點(diǎn)，直接將這個(gè)結(jié)點(diǎn)指向后驅(qū)。

1.2 刪除步驟

1.2.1 刪除結(jié)點(diǎn)不是頭結(jié)點(diǎn)

1. 定義 cur 從表的第二個(gè)結(jié)點(diǎn)開始遍歷。
   定義 prev 從表的 cur 的前驅(qū)位置開始遍歷。
   

   
   
   比較此時(shí) cur 指向結(jié)點(diǎn)的值是不是要?jiǎng)h除結(jié)點(diǎn)的值。
   是就改指向刪除，不是就 cur 往后面找。

2. 現(xiàn)在要?jiǎng)h除的是，值是2的結(jié)點(diǎn)。
   cur 此時(shí)指向了要?jiǎng)h除的結(jié)點(diǎn)，進(jìn)行改指向刪除。
   

   
   
   可以看到第一個(gè)節(jié)點(diǎn)直接指向了第三個(gè)節(jié)點(diǎn)。

3. cur 指向下一個(gè)，prev 指向 cur 的前驅(qū)。
   

   
   
   第一個(gè)節(jié)點(diǎn)存的是第三個(gè)節(jié)點(diǎn)的地址，也就與第二個(gè)結(jié)點(diǎn)斷開了。
   prev 此時(shí)不需要移動(dòng)即是 cur 的前驅(qū)。
   比較此時(shí) cur 指向結(jié)點(diǎn)的值是不是要?jiǎng)h除結(jié)點(diǎn)的值。
   是就改指向刪除，不是就 cur 往后面找。

4. 比較此時(shí) cur 指向結(jié)點(diǎn)的值是不是要?jiǎng)h除結(jié)點(diǎn)的。
   

   
   
   此時(shí)的第一個(gè)結(jié)點(diǎn)的地址域存的是最后一個(gè)結(jié)點(diǎn)的地址，也就指向了它。

5. cur 往后走，prev 指向cur的前驅(qū)。
   

   
   
   此時(shí) cur 指向結(jié)點(diǎn)的值不是要?jiǎng)h除的結(jié)點(diǎn)，cur指向下一個(gè)結(jié)點(diǎn)。
   
   
   
   此時(shí) cur 為空 遍歷結(jié)束，跳出循環(huán)。所有的要?jiǎng)h除的結(jié)點(diǎn)都已刪除完畢。
   
   

1.2.2 刪除的結(jié)點(diǎn)是頭結(jié)點(diǎn)的情況

如果頭結(jié)點(diǎn)是要?jiǎng)h除的結(jié)點(diǎn)，若按照上面的方法刪除；
遍歷結(jié)束后，頭結(jié)點(diǎn)是未刪除的。

可以看到此時(shí) cur 為空了，但是還有一個(gè)結(jié)點(diǎn)未刪除。

解決辦法：

判斷一下頭結(jié)點(diǎn)是不是要?jiǎng)h除的結(jié)點(diǎn)。

判斷方法：

• 將頭節(jié)點(diǎn)與要?jiǎng)h除的結(jié)點(diǎn)的值比較，看看是不是相等。
• 如果使得話，就直接將頭結(jié)點(diǎn)指向它的后區(qū)即可。

刪除后：

1.3 部分代碼思路分析

1. 如果表是空的直接返回

 //鏈表中可能是空的
 if(this.head == null) {
     return;
 }

2. 定義cur 和 prev

  ListNode cur = this.head.next;//cur指向要?jiǎng)h除的結(jié)點(diǎn)
  ListNode prev = this.head;//prev指向要?jiǎng)h除結(jié)點(diǎn)的前驅(qū)

3. 該結(jié)點(diǎn)指向代碼

prev.next = cur.next;//要?jiǎng)h除結(jié)點(diǎn)的前驅(qū)的地址域指向key結(jié)點(diǎn)的后驅(qū)的地址域
cur = cur.next;//要?jiǎng)h除的結(jié)點(diǎn)指向它的后驅(qū)

4. 判斷頭結(jié)點(diǎn)是不是要?jiǎng)h除的結(jié)點(diǎn)的代碼

if (this.head.value == key) {
    this.head = this.head.next;//將這個(gè)頭結(jié)點(diǎn)指向它的后驅(qū) - 然后就刪除了
}

1.4 整體代碼演示

//刪除所有key的結(jié)點(diǎn)
public void removeAllKey(int key) {
    //鏈表中可能是空的
    if(this.head == null) {
        return;
    }

    ListNode cur = this.head.next;//cur指向要?jiǎng)h除的結(jié)點(diǎn)
    ListNode prev = this.head;//prev指向要?jiǎng)h除結(jié)點(diǎn)的前驅(qū)
    //cur不等于空則說明cur未找到尾結(jié)點(diǎn)，移動(dòng)要繼續(xù)
    while (cur != null) {
       //如果當(dāng)前的cur指向的數(shù)據(jù)是我要找的key
       if (cur.value == key) {
           //改變指向刪除
           prev.next = cur.next;//要?jiǎng)h除結(jié)點(diǎn)的前驅(qū)的地址域指向key結(jié)點(diǎn)的后驅(qū)的地址域
           cur = cur.next;//要?jiǎng)h除的結(jié)點(diǎn)指向它的后驅(qū)
       }else{ //若不是要找的 - 跳到下一個(gè)結(jié)點(diǎn)
           prev = cur;//當(dāng)前cur結(jié)點(diǎn)的前驅(qū)指向cur指向的結(jié)點(diǎn)
           cur = cur.next;//當(dāng)前cur結(jié)點(diǎn)指向它的后驅(qū)
       }
   }
   //如果鏈表的第一個(gè)結(jié)點(diǎn)是key
   if (this.head.value == key) {
       this.head = this.head.next;//將這個(gè)頭結(jié)點(diǎn)指向它的后驅(qū) - 然后就刪除了
   }
}

2. 清空單鏈表

釋放單鏈表中每一個(gè)結(jié)點(diǎn)的對象，直接置為空即可。

代碼演示：

public void clear() {
   this.head = null;//將的結(jié)點(diǎn)置為空
}