java 实现删除单链表中所有指定的结点以及如何清空单链表

1. 删除单链表中的所有的指定结点

1.1 删除思路

• 定义一个 cur 来代替 head 遍历单链表。
• 遇到指定结点就开始删除。
• 是不是要删除的结点， cur 都指向下一个结点，直到表遍历完成。
• 单链表中可能没有要删除的结点。
• 定义一个 prev 指向要删除结点的前驱。
• 如果单链表的第一个结点就是要删除的结点，直接将这个结点指向后驱。

1.2 删除步骤

1.2.1 删除结点不是头结点

1. 定义 cur 从表的第二个结点开始遍历。
   定义 prev 从表的 cur 的前驱位置开始遍历。
   
   比较此时 cur 指向结点的值是不是要删除结点的值。
   是就改指向删除，不是就 cur 往后面找。

2. 现在要删除的是，值是2的结点。
   cur 此时指向了要删除的结点，进行改指向删除。
   
   可以看到第一个节点直接指向了第三个节点。

3. cur 指向下一个，prev 指向 cur 的前驱。
   
   第一个节点存的是第三个节点的地址，也就与第二个结点断开了。
   prev 此时不需要移动即是 cur 的前驱。
   比较此时 cur 指向结点的值是不是要删除结点的值。
   是就改指向删除，不是就 cur 往后面找。

4. 比较此时 cur 指向结点的值是不是要删除结点的。
   
   此时的第一个结点的地址域存的是最后一个结点的地址，也就指向了它。

5. cur 往后走，prev 指向cur的前驱。
   
   此时 cur 指向结点的值不是要删除的结点，cur指向下一个结点。
   
   此时 cur 为空 遍历结束，跳出循环。所有的要删除的结点都已删除完毕。
   

1.2.2 删除的结点是头结点的情况

如果头结点是要删除的结点，若按照上面的方法删除；
遍历结束后，头结点是未删除的。

可以看到此时 cur 为空了，但是还有一个结点未删除。

解决办法：

判断一下头结点是不是要删除的结点。

判断方法：

• 将头节点与要删除的结点的值比较，看看是不是相等。
• 如果使得话，就直接将头结点指向它的后区即可。

删除后：

1.3 部分代码思路分析

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

 //链表中可能是空的
 if(this.head == null) {
     return;
 }
1
2
3
4

2. 定义cur 和 prev

  ListNode cur = this.head.next;//cur指向要删除的结点
  ListNode prev = this.head;//prev指向要删除结点的前驱
1
2

3. 该结点指向代码

prev.next = cur.next;//要删除结点的前驱的地址域指向key结点的后驱的地址域
cur = cur.next;//要删除的结点指向它的后驱
1
2

4. 判断头结点是不是要删除的结点的代码

if (this.head.value == key) {
    this.head = this.head.next;//将这个头结点指向它的后驱 - 然后就删除了
}
1
2
3

1.4 整体代码演示

//删除所有key的结点
public void removeAllKey(int key) {
    //链表中可能是空的
    if(this.head == null) {
        return;
    }

    ListNode cur = this.head.next;//cur指向要删除的结点
    ListNode prev = this.head;//prev指向要删除结点的前驱
    //cur不等于空则说明cur未找到尾结点，移动要继续
    while (cur != null) {
       //如果当前的cur指向的数据是我要找的key
       if (cur.value == key) {
           //改变指向删除
           prev.next = cur.next;//要删除结点的前驱的地址域指向key结点的后驱的地址域
           cur = cur.next;//要删除的结点指向它的后驱
       }else{ //若不是要找的 - 跳到下一个结点
           prev = cur;//当前cur结点的前驱指向cur指向的结点
           cur = cur.next;//当前cur结点指向它的后驱
       }
   }
   //如果链表的第一个结点是key
   if (this.head.value == key) {
       this.head = this.head.next;//将这个头结点指向它的后驱 - 然后就删除了
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

2. 清空单链表

释放单链表中每一个结点的对象，直接置为空即可。

代码演示：

public void clear() {
   this.head = null;//将的结点置为空
}
1
2
3