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

蔚落 2023-10-02 22:12 31阅读 0赞

#### 文章目录 ####

*  1. 删除单链表中的所有的指定结点
 *   *  1.1 删除思路
     *  1.2 删除步骤
     *   *  1.2.1 删除结点不是头结点
         *  1.2.2 删除的结点是头结点的情况
     *  1.3 部分代码思路分析
     *  1.4 整体代码演示
 *  2. 清空单链表

![d57c3795684e498faa969db329da1670.jpeg_pic_center][]

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

### 1.1 删除思路 ###

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

### 1.2 删除步骤 ###

#### 1.2.1 删除结点不是头结点 ####

1.  定义 cur 从表的第二个结点开始遍历。  
    定义 prev 从表的 cur 的前驱位置开始遍历。  
    ![80fcc244460343b887124850070c2622.png_pic_center][]  
    比较此时 cur 指向结点的值是不是要删除结点的值。  
    是就改指向删除，不是就 cur 往后面找。
2.  现在要删除的是，值是2的结点。  
    cur 此时指向了要删除的结点，进行改指向删除。  
    ![81844ffc872f4a599f10b9dbbe850c20.png_pic_center][]  
    可以看到第一个节点直接指向了第三个节点。
3.  cur 指向下一个，prev 指向 cur 的前驱。  
    ![b44369301a9442d989c2c018fae1e55c.png_pic_center][]  
    第一个节点存的是第三个节点的地址，也就与第二个结点断开了。  
    prev 此时不需要移动即是 cur 的前驱。  
    比较此时 cur 指向结点的值是不是要删除结点的值。  
    是就改指向删除，不是就 cur 往后面找。
4.  比较此时 cur 指向结点的值是不是要删除结点的。  
    ![a677ad84ff8c42a491d81a1b80fdea94.png_pic_center][]  
    此时的第一个结点的地址域存的是最后一个结点的地址，也就指向了它。
5.  cur 往后走，prev 指向cur的前驱。  
    ![3a745d3af3944ec1a43572387dae7e58.png_pic_center][]  
    此时 cur 指向结点的值不是要删除的结点，cur指向下一个结点。  
    ![5772f4a492e6424aa537db4014d9d668.png_pic_center][]  
    此时 cur 为空 遍历结束，跳出循环。所有的要删除的结点都已删除完毕。  
    ![066d8e30f1b543ef9d497b6759e40e90.gif_pic_center][]

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

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

![3ba8482d367e4b5599ff3fff9281b6a6.png_pic_center][]  
可以看到此时 cur 为空了，但是还有一个结点未删除。

解决办法：

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

判断方法：

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

删除后：

![4ab88bc343cf460daf15851af35dc59c.png_pic_center][]

### 1.3 部分代码思路分析 ###

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

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

1.  定义cur 和 prev

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

1.  该结点指向代码

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

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

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

### 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;//将这个头结点指向它的后驱 - 然后就删除了
       }
    }

## 2. 清空单链表 ##

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

代码演示：

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

![e5cab273923b436c9f55f54a1da67f59.jpeg_pic_center][]

[d57c3795684e498faa969db329da1670.jpeg_pic_center]: https://img-blog.csdnimg.cn/d57c3795684e498faa969db329da1670.jpeg#pic_center
[80fcc244460343b887124850070c2622.png_pic_center]: https://img-blog.csdnimg.cn/80fcc244460343b887124850070c2622.png#pic_center
[81844ffc872f4a599f10b9dbbe850c20.png_pic_center]: https://img-blog.csdnimg.cn/81844ffc872f4a599f10b9dbbe850c20.png#pic_center
[b44369301a9442d989c2c018fae1e55c.png_pic_center]: https://img-blog.csdnimg.cn/b44369301a9442d989c2c018fae1e55c.png#pic_center
[a677ad84ff8c42a491d81a1b80fdea94.png_pic_center]: https://img-blog.csdnimg.cn/a677ad84ff8c42a491d81a1b80fdea94.png#pic_center
[3a745d3af3944ec1a43572387dae7e58.png_pic_center]: https://img-blog.csdnimg.cn/3a745d3af3944ec1a43572387dae7e58.png#pic_center
[5772f4a492e6424aa537db4014d9d668.png_pic_center]: https://img-blog.csdnimg.cn/5772f4a492e6424aa537db4014d9d668.png#pic_center
[066d8e30f1b543ef9d497b6759e40e90.gif_pic_center]: https://img-blog.csdnimg.cn/066d8e30f1b543ef9d497b6759e40e90.gif#pic_center
[3ba8482d367e4b5599ff3fff9281b6a6.png_pic_center]: https://img-blog.csdnimg.cn/3ba8482d367e4b5599ff3fff9281b6a6.png#pic_center
[4ab88bc343cf460daf15851af35dc59c.png_pic_center]: https://img-blog.csdnimg.cn/4ab88bc343cf460daf15851af35dc59c.png#pic_center
[e5cab273923b436c9f55f54a1da67f59.jpeg_pic_center]: https://img-blog.csdnimg.cn/e5cab273923b436c9f55f54a1da67f59.jpeg#pic_center