Java题目详解——LeetCode203. 移除链表元素

目录

题目链接：LeetCode203. 移除链表元素

一.题目要求

二.解题思路

1.循环遍历该链表

2.结点的删除 

3. 头结点的删除

三.具体代码

四.运行截图

---

题目链接：LeetCode203. 移除链表元素

一.题目要求

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

输入：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

二.解题思路

1.循环遍历该链表

        首先，我们看到此题的第一反应一定是要循环遍历该链表，并在循环时对链表进行一些操作。

循环遍历操作：

ListNode cur=head;
//循环遍历
while(cur!=null){
    cur=cur.next;
}

2.结点的删除 

        其次，应该在循环遍历的基础上进行特定结点的删除工作，当结点元素的值（cur.val）和传入值（val）相等时，删除该结点。

        比如上图，如果我们想删除 "6" 这个结点元素，让 "2" 直接指向 "3" ，从而实现删除 "6" 的操作，此时使要删除的结点（cur）为 "6" ，那么我们就需要一个结点来记录要删除结点（cur）的前驱结点（prev），从而使该结点（cur）的前驱结点（prev）直接指向该结点（cur）的后续结点（cur.next）。

        需要注意的是，需要删除cur时，prev不应该往后移动，因为删除后，下一个结点的前驱结点仍是该prev。

ListNode prev=null; //记录前驱结点 这种方式是错误的，后面会讲到
    while(cur!=null){
        if(cur.val==val){
            prev.next=cur.next;
        }else{
            prev=cur;
        }
        cur=cur.next;
   }

 3. 头结点的删除

        这时我们需要思考一个问题，如果头结点（head）是我们需要删除的元素，这样写还成立吗？

        答案是不成立的。原因在于，prev=null，如果使prev.next=cur.next，此时cur=head，这是两个解引用的操作，那么由于prev=null，对其进行解引用就会造成空指针异常，有以下两种解决方法：

        第一种就是分情况讨论，当cur==head时，返回head.next，作为新的头结点；

        第二种也就是如下这种方式，是先创建一个工具结点（fakeHead）指向head，使prev=fakeHead，也就是在头结点前面新创建了一个结点（fakeHead），这样就可以不用分情况讨论，最后返回fakeHead.next即可。

ListNode fakeHead=new ListNode();
fakeHead.next=head;
ListNode prev=fakeHead; //构造一个假结点

三.具体代码

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode cur=head;
        ListNode fakeHead=new ListNode();
        fakeHead.next=head;
        ListNode prev=fakeHead; //构造一个假结点
        while(cur!=null){
            if(cur.val==val){
                prev.next=cur.next;
            }else{
                prev=cur;
            }
            cur=cur.next;
        }
        return fakeHead.next;
    }
}

四.运行截图

如想了解链表（LinkedList）相关知识，请查阅：

LinkedList（链表）的介绍及自我实现

 如有建议或想法，欢迎一起讨论学习~