前言

什么是链表

链表是一种常见的数据结构，它通过一系列节点（Node）来存储数据。每个节点包含两个部分：一部分用于存储数据元素（称为数据域），另一部分用于存储指向下一个节点的指针（称为指针域或链域）。这些节点通过指针连接在一起，形成一条链。

链表具有很多独特的性质--他是有序的列表，具有线性的结构；链表所有的节点都是离散分布的，访问链表中任何一个节点都要从头节点开始逐个查找，因为他是单向列表，所以任一节点只能访问他的下一节点，无法回头访问。

链表节点的删除

中间删除节点

因为链表的两个性质：一个节点通过指针指向下一个节点；访问链表中任何一个节点都要从头开始逐个查找----所以如果我们要删除某个节点的话，我们只需要改变他指针的指向。对于节点123来说，要删除节点2需要改变节点1指针的指向，使节点1直接指向节点3

头部删除节点

删除中间的节点，我们只需要找到该节点前后的指针就行，但是如果我要删除头部节点该怎么办呢？

假设head是链表的头指针，并且链表不是空的，我们可以执行head=head.next这部操作。意思为将头指针向后移一位，设置新的头节点，新头节点前的节点丢失指针相当于被删除了。

虚拟头节点删除

通过创造虚拟头节点（Dummy Head Node）我们可以实现链表的从头开始的删除。虚拟头节点指向节点2，节点1被删除；虚拟头节点指向3，节点1节点2被删除。

在原链表中删除元素的代码规范

从头删除指向目标的所有节点

1. 首先我们要判断头节点不能为空，因为我们要利用头节点的指针head!=null
2. 我们拿着头指针使他移动，head = head.next
3. 直到他的下一位为我们的目标节点 head.next == target
4. 这个过程是持续移除的while

while(head!=null && head.next == target){
    head = head.next;
}

删除链表中间的元素

1. 我们定义一个临时指针cur(current)指向head let = head
2. 确保cur不为空，cur的下一个节点也不为空 cur ！= null && cur.next != null
3. 循环遍历链表，知道当前节点或当前节点的下一个节点为空时停止循环 while (cur !== null && cur.next !== null)
4. 当当前节点的下一个节点的值等于目标值（你需要删除的值）时，cur.next.value === target
5. 跳过这个值，将当前节点的下下个值赋给下个值，实现删除当前节点下个值的效果 cur.next = cur.next.next
6. 如果当前节点的下一个节点的值不等于目标值，则向前移动 cur = cur.next
7. 重新返回头节点访问这个新链表 return head

适用场景：手搓一个函数能够删除链表中的target值

function removeTarget(head, target) {
    let cur = head;
    // 循环遍历链表，直到当前节点为空或者下一个节点为空  
    while (cur !== null && cur.next !== null) {
        // 如果下一个节点的值等于目标值 target  
        if (cur.next.value === target) {
            // 则将当前节点的next指针指向下一个节点的下一个节点  
            // 这样就跳过了值为target的节点，实现了删除效果  
            cur.next = cur.next.next;
        } else {
            // 如果下一个节点的值不等于target，则继续遍历链表  
            cur = cur.next;
        }
        // 注意：这里不应该有return语句，因为它会提前结束函数  
    }

    // 遍历完链表后返回头节点（在JavaScript中，这通常是函数的最后一行）  
    return head;

}

使用虚拟头节点的删除规范--“哑节点”（dummy node）使用技巧

目的：利用“哑节点”技巧手搓一个函数能够删除链表中的target值

构思：

1. 哑节点也称哨兵节点，我们需要将虚拟节点实例化，这样我们才能够使用他。我们通常会用ListNode去行使链表节点的功能和属性 let dummyhead = new ListNode(0);传入的 0 是这个哑节点的值，使用 0 或其他不会出现在链表中的值作为哑节点的值，只是为了确保在后续的操作中不会与链表中的实际数据节点混淆。

2. 我们为什么要使用哑节点？因为我们想--如果有个虚拟节点在头节点之前，无论是对于头节点还是后续节点的删除修改都会便捷很多；所以我们将dummy的指针指向head，将他放在头指针的前面。 dummyhead.next = head;

3. 直接使用头指针进行遍历去查找目标节点会导致丢失链表应用等一系列问题所以我们需要临时指针cur来帮我们遍历。 let cur = dummyhead;

4. 使用while循环遍历，cur的下一个节点为空。 while (cur.next !== null)

5. 在遍历过程中，如果cur.next的值为target则跳过这个节点，将cur链接到cur.next.next上。 cur.next.value === target--> cur.next = cur.next.next;

6. 如果cur.next的值不为target就继续向前遍历。 cur = cur.next;

7. 最后返回修改后的数组，修改后的数组不包括虚拟头节点，所以返回dommy.next。使用dommy.next比直接返回head的安全性更高，因为头节点可能被删除。 return dummyhead.next;

function removeTarget(head, target) {
    // 创建一个哑节点作为新链表的头  
    let dummyhead = new ListNode(0); // 使用一个不会出现在链表中的值  
    dummyhead.next = head;

    let cur = dummyhead;

    // 遍历链表  
    while (cur.next !== null) {
        // 如果下一个节点的值等于目标值，则删除它  
        if (cur.next.value === target) {
            cur.next = cur.next.next;
        } else {
            // 否则，继续遍历链表  
            cur = cur.next;
        }
        // 注意：return 语句被移出了 while 循环  
    }

    // 遍历完成后返回哑节点的下一个节点，即新链表的头节点  
    return dummyhead.next;
}  

这个函数手搓完成，他可以实现如下功能：

如果有如下链表， let node1 = new ListNode(1); let node2 = new ListNode(2); let node3 = new ListNode(3); node1.next = node2; node2.next = node3; 那么 let newHead = removeTarget(node1, 2); 将把值为2的node2删除，node1直接与node3相连。

深度思考： 直接遍历 和 运用虚拟节点的遍历条件为什么不同？

while (cur !== null && cur.next !== null) 和 while (cur.next !== null)的不同是 因为直接在链表中被删除的节点可能刚好是头节点，当我们运用虚拟节点定义在头节点前时，就算被删除的是头节点也能很好的被判断到；但是直接遍历时我们需要另外处理头节点被删除的情况。

所以其实原因就一点：他们的临时指针cur的指向不同，临时指针指向头指针需要考虑头节点被删除的情况所以要多考虑自身为空的情况

• 不使用虚拟节点时，需要处理头节点被删除的特殊情况，并可能需要一个额外的检查来找到新的头节点。
• 使用虚拟节点时，不需要担心头节点的特殊处理，因为虚拟节点提供了一个固定的起点，你可以从这个起点开始安全地遍历和删除节点。

小结

经过本次的学习我们掌握了删除链表中节点的方法，在下一篇章中我们将详细讲解LeetCode203，21，136，83等题