| 2024-04-06 |

# 移除链表元素

前言：这题在 4 天前差不多 4 月 2 日我写了一次所以相对更加熟悉了一些。画了两百个馒头进算法训练营，发现用 C# 的小伙伴真的好少啊，突然开始觉得自己又花冤枉钱了。而且同时要肝项目还要刷算法还想打游戏真的好难啊。项目上又遇到难关了。本来应该抽离出来的数据一开始没考虑好抽离。现在复制黏贴功能不好弄咯。下次不能犯这种错误了。

# 题目

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

示例 1：

img
1
2
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
示例 2：
1
2
输入：head = [], val = 1
输出：[]
示例 3：
1
2
输入：head = [7,7,7,7], val = 7
输出：[]
提示：

列表中的节点数目在范围 [0, 104] 内

1 <= Node.val <= 50

0 <= val <= 50

在两天前我是没设定一个虚假的头结点的

# 题解 1

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode RemoveElements(ListNode head, int val) {
        //移除头结点
        while ( head!=null && head.val == val){
            //新的头结点向后移动
            head = head.next;
        }
        if (head == null) 
        {
            return head;
        }
        ListNode curNode;
        ListNode preNode; //上一个节点
        preNode = head;
        curNode = head.next; 
        //非头节点 如果下一个节点不为空(不是末尾节点) 且当前节点
        while(curNode != null)
        {
           if(curNode.val == val){
            //上一个节点指向当前节点的下一个
            preNode.next = curNode.next;
            curNode = null;
           }else{
                preNode = preNode.next;
           }
           
           curNode = preNode.next;
        }

        return head;
    }
}

然后今天这个是设立了虚假头结点的

# 题解 2

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode RemoveElements(ListNode head, int val) {
        //定义一个虚拟头结点 StartNode.next 为头结点
        ListNode StartNode = new();
        ListNode curNode = head;
        ListNode LastNode = StartNode;
        StartNode.next = head;
        //如果移除的是头结点
        if(head != null && head.val == val){
            StartNode.next = head.next;
        }
        if(StartNode.next == null){
            return StartNode.next;
        }

        while(curNode != null){
            if(curNode.val == val)
            {
                LastNode.next = curNode.next;
                curNode = null;
            }else
            {
                LastNode = LastNode.next;
            }
            //这里关键要注意一下 当前节点始终在前一个节点的下一个
            curNode = LastNode.next;
        }
        return StartNode.next;
    }
}

嗯

所以说上一个节点是命名为 preNode 好还是 lastNode 好呢

好纠结

tags: #算法