【数据结构算法篇】链表面试题2—删除链表中等于给定值 val 的所有节点

妖狐艹你老母 2023-09-27 11:22 97阅读 0赞

> 专栏：[《数据结构必刷题》][Link 1]  
> 大家如果对数据结构的题感兴趣的话，可以订阅一下我的专栏，谢谢！

题目来自：**力扣**  
传送门：[点击即可跳转][Link 2]

题目：移除链表元素  
题目描述：给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。  
示例1：  
![在这里插入图片描述][6d84775a654544fdb664421191471956.png]

> 输入：head = \[1,2,6,3,4,5,6\], val = 6  
> 输出：\[1,2,3,4,5\]

示例2：

> 输入：head = \[\], val = 1  
> 输出：\[\]

示例3：

> 输入：head = \[7,7,7,7\], val = 7  
> 输出：\[\]

提示：

> 列表中的节点数目在范围 \[0, 104\] 内  
> 1 <= Node.val <= 50  
> 0 <= val <= 50

解题思路：  
对于数据结构，我会采用画图进行解题。下面给大家分享一下我的解题思路，请看下图：  
![在这里插入图片描述][1efa4fb1a65049f986f3c83dc4107291.png]  
这是示例1的输入输出样例，上面的地址是我随便写的，只是为了让大家更好的理解数据结构。这道题还是挺简单的。  
**只需要让等于val值的那个结点的前一个结点的指针域改成val值结点的指针域就可以了，就可以实现逻辑上的删除，如上图中的第二个结点的指针域改成了第三个结点的指针域，因当我们遍历的时候，它会从第二个结点直接跳到第四个结点，而倒数第二个节点的指针域为null,当遍历到这时就直接停止了，就不会在遍历最后一个结点了。于是便实现了逻辑上的删除。**  
如下：  
![在这里插入图片描述][51136cab019f49329c5159a17f45784d.png]  
这样就可以删掉具有val的结点。只需要加上一些循环条件以及遇到不是val值得结点时的条件就可以了，如下：

while(cur != null){
        
                if(cur.val == val){
        
                    prev.next = cur.next;
                    cur = cur.next;
                 }else{
        
                     prev = cur;
                     cur = cur.next;
                 }
            }

以上代码就可以解决很多问题。但是也有隐患，会出现一些特殊情况。  
 特殊情况 \\color\{\#FF0000\}\{特殊情况\} 特殊情况：**1.空链表 2.链表的第一个结点值是val**

空链表的情况 \\color\{\#FF0000\}\{空链表的情况\} 空链表的情况  
空链表的情况处理起来很简单，**直接返回null**就行了。主要是是否能想到空链表的这个情况，其实对于数据结构的链表题，**只要题目中不说明不可能是空链表，就要首先考虑到空链表的情况**。

链表的第一个结点值是 v a l \\color\{\#FF0000\}\{链表的第一个结点值是val\} 链表的第一个结点值是val  
其实这个处理也很简单，上面那段代码可以删除第二个结点以后值是val的结点，那么就只需要在后面判断一下头节点的值是不是val，如果是val就让head = head.next 这样就可以了。  
这里有一点要注意一下，**判断头节点值是否为val，一定要在循环后面，也就是删除完后面节点的值是val的之后。如果在循环前判断会遇到一些问题，那就是如果第二个结点也是val，那就相当于还是没有删除头节点是val的这种情况**。  
完整代码：

public ListNode removeElements(ListNode head, int val) {
        
            if(head == null){
        
                return null;
            }
            ListNode cur = head.next;
            ListNode prev = head;
            while(cur != null){
        
                if(cur.val == val){
        
                    prev.next = cur.next;
                    cur = cur.next;
                 }else{
        
                     prev = cur;
                     cur = cur.next;
                 }
            }
            if(head.val == val){
        
                head = head.next; 
            }
            return head;
        }

运行截图：  
![在这里插入图片描述][8e8adf339df945febd09fe888f439833.png]

[Link 1]: https://blog.csdn.net/m0_63463510/category_12021169.html?spm=1001.2014.3001.5482
[Link 2]: https://leetcode.cn/problems/remove-linked-list-elements/description/
[6d84775a654544fdb664421191471956.png]: https://img-blog.csdnimg.cn/6d84775a654544fdb664421191471956.png
[1efa4fb1a65049f986f3c83dc4107291.png]: https://img-blog.csdnimg.cn/1efa4fb1a65049f986f3c83dc4107291.png
[51136cab019f49329c5159a17f45784d.png]: https://img-blog.csdnimg.cn/51136cab019f49329c5159a17f45784d.png
[8e8adf339df945febd09fe888f439833.png]: https://img-blog.csdnimg.cn/8e8adf339df945febd09fe888f439833.png