本文由 简悦 SimpRead 转码， 原文地址 programmercarl.com
203.移除链表元素
题意
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点
输入：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
输出：[]
举例
这里以链表 1 4 2 4 来举例，移除元素 4。
如果使用 C，C++ 编程语言的话，不要忘了还要从内存中删除这两个移除的节点， 清理节点内存之后如图：
当然如果使用 java ，python 的话就不用手动管理内存了。
还要说明一下，就算使用 C++ 来做 leetcode，如果移除一个节点之后，没有手动在内存中删除这个节点，leetcode 依然也是可以通过的，只不过，内存使用的空间大一些而已，但建议依然要养生手动清理内存的习惯。
链表操作的两种方式
上面这种情况下的移除操作，就是让节点 next 指针直接指向下下一个节点就可以了，
因为单链表的特殊性，只能指向下一个节点，如果删除的是头结点又该怎么办呢？
这里就涉及如下链表操作的两种方式：
- 直接使用原来的链表来进行删除操作。
- 设置一个虚拟头结点在进行删除操作。
直接使用原来的链表
来看第一种操作：直接使用原来的链表来进行移除。
链表的其他节点都是通过前一个节点来移除当前节点，而头结点没有前一个节点。所以移除头结点和移除其他节点的操作是不一样的
所以头结点如何移除呢，其实只要将头结点向后移动一位就可以，这样就从链表中移除了一个头结点。
依然别忘将原头结点从内存中删掉。 
这样移除了一个头结点，是不是发现，在单链表中移除头结点 和 移除其他节点的操作方式是不一样，其实在写代码的时候也会发现，需要单独写一段逻辑来处理移除头结点的情况。
那么可不可以 以一种统一的逻辑来移除 链表的节点呢。
哨兵：设置一个虚拟头结点
哨兵节点在树和链表中被广泛用作伪头、伪尾等，通常不保存任何数据。来简化插入和删除
其实可以设置一个虚拟头结点，这样原链表的所有节点就都可以按照统一的方式进行移除了。
来看看如何设置一个虚拟头。依然还是在这个链表中，移除元素 1。
这里来给链表添加一个虚拟头结点为新的头结点，就可以使用和移除链表其他节点的方式统一了
最后 return 头结点的时候，别忘了 return dummyNode->next;， 这才是新的头结点
Go：
方法一：迭代
/*** Definition for singly-linked list.* type ListNode struct {* Val int* Next *ListNode* }*/func removeElements(head *ListNode, val int) *ListNode {//dummyHead := &ListNode{} // 设置一个虚拟头结点//dummyHead.Next = head // 将虚拟头结点指向head，这样方便后面做删除操作dummyHead := &ListNode{Next: head} // 设置虚拟头结点，并将其next指向头结点tmp := dummyHeadfor tmp.Next != nil {if tmp.Next.Val == val {tmp.Next = tmp.Next.Next // 满足条件：tmp.Next 往后跳一个元素，这样就断开了原先的顺序，} else {tmp = tmp.Next // 不满足条件：tmp等于下一个元素就行；tmp.next正常按照之前的顺序}}return dummyHead.Next}
复杂度分析
- 时间复杂度：O(n)，其中 n 是链表的长度。需要遍历链表一次。
- 空间复杂度：O(1)。
本地运行
在设计链表的代码基础上，进行测试。
package main
import (
"fmt"
)
type MyLinkedList struct {
// 申明指针，指向 Node结构体 的指针
Dummy *Node //定义一个虚拟头结点，
}
// 定义链表节点结构体
type Node struct {
Val int
Next *Node
Pre *Node
}
func main() {
var ml = Constructor()
fmt.Printf("ml=%+v\n", ml) // ml={Dummy:0xc0000a6020}
fmt.Printf("ml.Dummy=%+v\n", ml.Dummy) // ml.Dummy=&{Val:-1 Next:0xc00000c080 Pre:0xc00000c080}
fmt.Printf("ml.Dummy.Next=%+v\n", ml.Dummy.Next) // ml.Dummy.Next=&{Val:-1 Next:0xc0000a6020 Pre:0xc0000a6020}
fmt.Printf("ml.Dummy.Next.Next=%+v\n", ml.Dummy.Next.Next) // ml.Dummy.Next.Next=&{Val:-1 Next:0xc00011c020 Pre:0xc00011c020}
//bs, _ := json.Marshal(ml)
//var out bytes.Buffer
//json.Indent(&out, bs, "", "\t")
//fmt.Printf("MyLinkedList=%v\n", out.String())
fmt.Printf("初始虚拟头结点 Dummy=%+v\n", ml.Dummy.Val) // Dummy=-1
fmt.Printf("初始获取Get index=1:%+v\n", ml.Get(1)) // Get:-1
fmt.Println("AddAtHead 3")
ml.AddAtHead(3)
fmt.Printf("ml.Dummy.Pre.Val=%+v\n", ml.Dummy.Pre.Val) // ml.Dummy.Pre.Val=3
fmt.Printf("ml.Dummy.Next.Val=%+v\n", ml.Dummy.Next.Val) // ml.Dummy.Next.Val=3
fmt.Println("AddAtHead 2")
ml.AddAtHead(2)
fmt.Printf("ml.Dummy.Pre.Val=%+v\n", ml.Dummy.Pre.Val) // ml.Dummy.Pre.Val=3
fmt.Printf("ml.Dummy.Next.Val=%+v\n", ml.Dummy.Next.Val) // ml.Dummy.Next.Val=2
fmt.Println("AddAtHead 1")
ml.AddAtHead(1)
fmt.Printf("ml.Dummy.Pre.Val=%+v\n", ml.Dummy.Pre.Val) // ml.Dummy.Pre.Val=3
fmt.Printf("ml.Dummy.Next.Val=%+v\n", ml.Dummy.Next.Val) // ml.Dummy.Next.Val=1
fmt.Printf("Get index=-1:%+v\n", ml.Get(-1)) // Get:-1
fmt.Printf("Get index=0:%+v\n", ml.Get(0)) // Get:-1
fmt.Printf("Get index=1:%+v\n", ml.Get(1)) // Get:-1
fmt.Printf("Get index=2:%+v\n", ml.Get(2)) // Get:-1
fmt.Printf("Get index=3:%+v\n", ml.Get(3)) // Get:-1
// 头结点
headNdoe := ml.returnHeadNode();
newHN := ml.removeElements(headNdoe,1) //删除val=1的节点，并返回新的头结点。
fmt.Printf("新的头结点：%+v\n",newHN)
}
// go语言没有面向对象。没有析构函数；力扣规定，程序会先执行Constructor函数进行初始化工作
// 初始化链表，是双向循环链表，首尾相连
// 此时结构体MyLinkedList为：Dummy:rear{Val: -1,Next: rear,Pre: rear,} 嵌套自身的结构体是无限循环的，无法直接打印，循环遍历的话也是无限值
// 但是只要判断Dummy.Next是否和Dummy相等，就可以知道Dummy.Next是否是空的节点，从而终止循环。
func Constructor() MyLinkedList {
rear := &Node{
Val: -1,
Next: nil,
Pre: nil,
}
rear.Next = rear
rear.Pre = rear
return MyLinkedList{rear} // 给结构体顺序赋值，不用写键名Dummy: rear
}
// 函数方法：给结构体MyLinkedList绑定函数
// get(index)：获取链表中第 index 个节点的值（从0开始）。如果索引无效，则返回 - 1。
// 如原链表为：Dummy<->1<->2<->3<->4，index=2，找到3
// 1 过滤掉虚拟节点 1<->2<->3<->4
// 2 遍历链表，如果index为负数，返回-1；如果index=0，就是头结点的值；
func (this *MyLinkedList) Get(index int) int {
head := this.Dummy.Next // 虚拟头节点的next为真正的头结点开始的地方
// 遍历链表
//head == this.Dummy, 说明Dummy和head都是同一个Node空节点，说明head为空节点了，没有后续的节点了。
for head != this.Dummy && index > 0 {
index-- // 第n个链表的值，只能遍历获取，每次-1就，直到index=0就能找到第n个节点的值(前提是索引index有效，没超出链表的大小)
head = head.Next // head.Next 为下一个节点
}
// 如果链表只有5个值，参数index的值最大为4（索引从0开始），如果参数index=5；最后发现下一个节点为空了，此时index=1，有效的索引index最后应该为0
// 遍历完链表后，index不等于1；就是无效的索引，超出链表的大小了；规定返回-1即可
if index != 0 {
return -1
}
// 索引有效的情况，返回查到的链表值
return head.Val
}
// 链表头部增加值：
// 依次增加3，2，1到头结点，链表为：3<->Dummy<->1<->2<->3
func (this *MyLinkedList) AddAtHead(val int) {
Dummy := this.Dummy // 虚拟头节点
// 1 给新头节点的next为原头节点，pre为虚拟节点：
node := &Node{
Val: val, // 3
Next: Dummy.Next, // 3->-1，Dummy.Next为真正的头结点。将其放在新的头结点后面；如果第一次添加值，Dummy.next是空的，
Pre: Dummy, // -1<- 3 ->-1 头节点的上一个节点总是虚拟节点
}
// 2 将原头节点的pre改为新的头结点：
// 上面node.Next.pre的值也修改为node了
Dummy.Next.Pre = node
// 3 将虚拟节点的next改为新的头节点
//此时的node,已经把上面的结果包含了，也就是node.next。pre=node；此时把拼接好的node，放在虚拟节点的后面即可。
Dummy.Next = node
}
// 链表尾部添加值
// 如原链表为：Dummy<->1<->2<->3；将4添加到尾部
func (this *MyLinkedList) AddAtTail(val int) {
Dummy := this.Dummy
// 1 给尾节点的next为空节点，这里可以是Dummy节点，因为它就是空节点；pre为
rear := &Node{
Val: val,
Next: Dummy, // 尾节点的下一个是虚拟dummy节点，首尾相连
Pre: Dummy.Pre, // 尾结点的上一个是原尾结点，dummy的pre就是尾结点。
}
// 2原尾结点的下一个为 新的尾节点
Dummy.Pre.Next = rear
// 虚拟节点的上一个为新的尾节点。
Dummy.Pre = rear
}
//在链表中的第 index 个节点之前添加值为 val 的节点。
//如果 index 等于链表的长度，则该节点将附加到链表的末尾。(正常逻辑满足条件)
//如果 index 大于链表长度，则不会插入节点。（判断）
//如果 index 小于 0，则在头部插入节点。 （index小于0，head就是头结点，满足）
func (this *MyLinkedList) AddAtIndex(index int, val int) {
head := this.Dummy.Next
for head != this.Dummy && index > 0 {
head = head.Next
index--
}
// 如果index大于0，说明超出链表长度，不操作
if index > 0 {
return
}
// 插入的节点的前后关系。
node := &Node{
Val: val,
Next: head,
Pre: head.Pre,
}
// 前面节点的下一个为新节点
head.Pre.Next = node
// 后面的节点上一个为新的节点。
head.Pre = node
}
//如果索引 index 有效，则删除链表中的第 index 个节点。
func (this *MyLinkedList) DeleteAtIndex(index int) {
//空链表，直接返回
if this.Dummy.Next == this.Dummy {
return
}
//头节点
head := this.Dummy.Next
//
for head.Next != this.Dummy && index > 0 {
head = head.Next
index--
}
//只有index等于0，说明索引有效；大于0说明超出链表长度，
if index == 0 {
// 1将要删除的节点的下一个的pre为：要删除的节点的上一个
head.Next.Pre = head.Pre
// 2将要删除的节点的上一个的下一个为：要删除的节点的下一个。
head.Pre.Next = head.Next
}
}
// 返回头结点
func (this *MyLinkedList) returnHeadNode() *Node{
return this.Dummy.Next
}
// 移除链表元素
// 给你一个链表的头节点 head 和一个整数 val;删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点
func (this *MyLinkedList) removeElements(head *Node, val int) *Node{
//dummyHead := &Node{} // 设置一个虚拟头结点；假设head节点没有pre虚拟节点。重新生成一个虚拟节点。
//dummyHead.Val=-1;
//dummyHead.Next = head // 将虚拟头结点指向head，这样方面后面做删除操作
//dummyHead.Pre=nil
dummy := head.Pre
tmp := dummy
// head不为空节点
for tmp.Next != this.Dummy {
if tmp.Next.Val == val {
tmp.Next = tmp.Next.Next // 满足条件：tmp.Next 往后跳一个元素，这样就断开了原先的顺序，
tmp.Next.Next.Pre = tmp.Next
} else {
tmp = tmp.Next // 不满足条件：tmp等于下一个元素就行；tmp.next正常按照之前的顺序
}
}
return dummy.Next
}
若有收获，就点个赞吧
0 人点赞
