如何删除单链表中第一次出现的某个节点

迷南。 2023-10-02 22:11 10阅读 0赞

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

*  删除单链表第一次出现的结点
 *   *  思路
     *  步骤
     *   *  1. 遍历单链表，找到要删除的节点后，使del指向这个位置。
         *  2. 单链表中可能没有key这个结点。
         *  3. key在头结点的情况
         *  4. 查找key方法的实现
         *  5. 改变结点的指向来实现删除key
     *  代码实现

![249c7d2b8c3f4c54b53e6dfde1d27262.jpeg_pic_center][]

## 删除单链表第一次出现的结点 ##

删除前  
  
![e664163cdb594cac9248defa388352a4.png_pic_center][]  
  
删除后  
  
![95db068258254f47926472dcc5571d9c.png_pic_center][]  
head直接指向了del结点的下一个节点，key就相当于是断掉了链接。

### 思路 ###

*  定义一个del，指向要删除的结点。
 *  写一个方法查找单链表中有没有这个结点。
 *  需要判断单链表在不在头结点的位置。
 *  单链表不能是空的。
 *  改变要删除结点的前一个结点的指向，使其直接指向key的后一个结点。

### 步骤 ###

#### 1. 遍历单链表，找到要删除的节点后，使del指向这个位置。 ####

![c8d94c899fd2471a9da33bc304f7abd3.png_pic_center][]*上图中del指向的结点就是要删除的结点。*

#### 2. 单链表中可能没有key这个结点。 ####

![b53e2d82cb7d4d5eb298fd4027ca0309.png_pic_center][]  
*上图中要删除的是存放4数据的结点，但是遍历完之后也找不到这个结点，所以单链表中没有这个结点。  
如果没有key结点，直接返回即可。*

#### 3. key在头结点的情况 ####

删除前：  
![a0c553ba077d471aba956a0409ce78eb.png_pic_center][]  
删除后：  
![0a57428993bd477395de509a4df5b0a4.png_pic_center][]  
*上图中要删除的是存放1数据的结点，很明显是单链表的头结点。  
如果是这样的话，可以直接让head指向head的下一个结点，将这个结点定位新的头结点。*

#### 4. 查找key方法的实现 ####

*  遍历单链表。
 *  每次遇到一个结点，都与key比较看看是不是要删除的结点。
 *  如果遍历结束未找到key结点，说明单链表中不存在key，直接返回null。

private ListNode findPrevOfKey(int key) {
         //查找key前一个结点的方法
        ListNode cur = this.head;//代替head向后移动
        //当cur指向链表尾结点的前一个结点时整个链表就判断完了
        while (cur.next != null) {
        
           //cur指向的地址域，再指向这个地址的数据域里的数据
           if (cur.next.value == key) {
        
               return cur;//找到了key的前一个位置，此时cur就是key的前一个结点
           }
           cur = cur.next; //没找到调整
        }
        //代码走到这里肯定为空
        return null;//返回null说明没找到
    }

#### 5. 改变结点的指向来实现删除key ####

![cd1a485bfb8c4946a0f909b454324c6f.png_pic_center][]

*  先让del指向cur的下一个结点，**del = cur.next**。

![5bc9d0d1301046bdb8ace32bae1c9328.png_pic_center][]

*  改变cur结点的指向，来删除的了结点，**cur.next = del.next**。  
    ![49465ea341ab49f19d34e454a9226428.png_pic_center][]  
    删除一个结点就像是把一个条铁链的一个铁环去掉是一样的。  
    **需要将去掉铁环的前一个铁环于去掉铁环的下一个铁环链接起来**，不然无法组成一个铁链。

### 代码实现 ###

//删除第一次出现的key结点
    public void remove(int key) {
        
        //key不能超过表的长度
        //先找到要删除的key结点的前一个结点，然后改变这个结点的指向，使其指向key结点的后一个结点
        //链表有可能是空的 - 判断一下
        if (this.head == null) {
        
            return;
        }
        //第一种情况是key在头结点 - 直接向后移动
        if (this.head.value == key) {
        
            this.head = this.head.next;//头结点指向头结点的下一个结点
            return;
        }
        //程序走到这里说明链表不是空的，而且key不在头结点处
        ListNode cur = findPrevOfKey(key);//调用此方法后此时cur指向的是key的前一个结点
        //链表中有可能没有key结点
        if (cur == null) {
        
            System.out.println("链表中没有这个结点！！！");
            return;
        }
        //定义一个del结点，del是要删除的结点
        ListNode del = cur.next;//cur.next指向的是要删除的结点
    
        //删除
        cur.next = del.next;//当前key结点的前一个结点的地址域指向要删除结点的下一个结点的地址域
    }
    
    private ListNode findPrevOfKey(int key) {
         //查找key前一个结点的方法
        ListNode cur = this.head;//代替head向后移动
        //当cur指向链表尾结点的前一个结点时整个链表就判断完了
        while (cur.next != null) {
        
           //cur指向的地址域，再指向这个地址的数据域里的数据
           if (cur.next.value == key) {
        
               return cur;//找到了key的前一个位置，此时cur就是key的前一个结点
           }
           cur = cur.next; //没找到调整
        }
        //代码走到这里肯定为空
        return null;//返回null说明没找到
    }

**注**

*  代码中的head表示头结点。
 *  key是要删除结点中的值。
 *  findPrevOfKey()是用来查找key结点是否存在的方法。  
    ![c9d809e04eb84756a108b41bfe7963c4.jpeg_pic_center][]

[249c7d2b8c3f4c54b53e6dfde1d27262.jpeg_pic_center]: https://img-blog.csdnimg.cn/249c7d2b8c3f4c54b53e6dfde1d27262.jpeg#pic_center
[e664163cdb594cac9248defa388352a4.png_pic_center]: https://img-blog.csdnimg.cn/e664163cdb594cac9248defa388352a4.png#pic_center
[95db068258254f47926472dcc5571d9c.png_pic_center]: https://img-blog.csdnimg.cn/95db068258254f47926472dcc5571d9c.png#pic_center
[c8d94c899fd2471a9da33bc304f7abd3.png_pic_center]: https://img-blog.csdnimg.cn/c8d94c899fd2471a9da33bc304f7abd3.png#pic_center
[b53e2d82cb7d4d5eb298fd4027ca0309.png_pic_center]: https://img-blog.csdnimg.cn/b53e2d82cb7d4d5eb298fd4027ca0309.png#pic_center
[a0c553ba077d471aba956a0409ce78eb.png_pic_center]: https://img-blog.csdnimg.cn/a0c553ba077d471aba956a0409ce78eb.png#pic_center
[0a57428993bd477395de509a4df5b0a4.png_pic_center]: https://img-blog.csdnimg.cn/0a57428993bd477395de509a4df5b0a4.png#pic_center
[cd1a485bfb8c4946a0f909b454324c6f.png_pic_center]: https://img-blog.csdnimg.cn/cd1a485bfb8c4946a0f909b454324c6f.png#pic_center
[5bc9d0d1301046bdb8ace32bae1c9328.png_pic_center]: https://img-blog.csdnimg.cn/5bc9d0d1301046bdb8ace32bae1c9328.png#pic_center
[49465ea341ab49f19d34e454a9226428.png_pic_center]: https://img-blog.csdnimg.cn/49465ea341ab49f19d34e454a9226428.png#pic_center
[c9d809e04eb84756a108b41bfe7963c4.jpeg_pic_center]: https://img-blog.csdnimg.cn/c9d809e04eb84756a108b41bfe7963c4.jpeg#pic_center