【12.24】转行小白历险记-刷算法03-拓冰建站

昨天刷着刷着忘记笔记了，不太好复盘，今天记得

咋们就是说狠狠笔记，发现自己的短板与不足

一、链表

01--203.移除链表元素

1.方法

1.1虚拟头节点实现链表的删除操作

1.链表的删除是让上一个几点指向下一个节点的头部，但是头部节点可以直接指向下一个节点的头部

2.使用虚拟节点删除链表中的元素主要是为了简化代码逻辑，特别是在处理头节点的增删操作时，可以避免对特殊情况的额外处理

1.不使用虚拟节点删除链表的逻辑过程

var removeElements = function(head, val) {// 删除头节点while (head !== null && head.val === val) {head = head.next;}// 删除非头节点let cur = head;while (cur !== null && cur.next !== null) {if (cur.next.val === val) {cur.next = cur.next.next;} else {cur = cur.next;}}return head;
};

代码解释

删除头节点:
- 使用 while 循环检查头节点是否需要删除（即头节点的值等于 val）。
- 如果需要删除，将头节点更新为下一个节点。
删除非头节点:
- 使用另一个 while 循环遍历链表。
- let cur = head; 这一步是为了在不改变头节点引用的前提下遍历和操作链表
- 如果当前节点的下一个节点的值等于 val，则删除该节点。
返回头节点:
- 在删除操作完成后，返回更新后的头节点。

回顾一下while和if的区别

while 和 if 是两种基本的控制结构，它们在编程中扮演不同的角色。理解这两者的区别对于编写有效的代码非常重要。

`if` 语句

用途：if 语句用于基于特定条件执行一段代码。如果该条件为真（true），则执行 if 块内的代码；如果为假（false），则跳过该代码块。
一次性检查：if 语句仅在条件首次评估时检查一次。不论条件之后如何变化，if 块内的代码只会基于最初的条件检查被执行或跳过。

`while` 循环

用途：while 循环用于在条件为真时重复执行代码块。只要条件保持为真，循环就会继续进行。
重复检查：在 while 循环中，条件在每次循环开始时都会被检查。如果条件为真，循环体中的代码会被执行，然后再次检查条件；如果条件为假，循环将结束。

比较

执行次数：if 语句是单次执行的（只有当条件为真时），而 while 循环可以执行多次（只要条件保持为真）。
用途：if 语句用于条件性执行代码，while 循环用于重复执行代码，直到条件不再满足。

根据你的需求，你可以选择使用 if 来执行一次性的条件判断，或者使用 while 循环来执行重复的任务，直到满足某个停止条件。

2.使用虚拟节点删除链表的逻辑过程

2.1 虚拟节点

const ret = new ListNode(0, head);

2.2初始化节点

function ListNode(val, next) {this.val = val === undefined ? 0 : val;this.next = next === undefined ? null : next;
}

现在差不多理解了，但是不知道真是不是理解了

02------设计链表

1.虚拟节点

constructor() {this.dummyHead = new ListNode(0);this.size = 0;}

2.获取第n个节点的值

get(index) {// 1. 检查索引的有效性if (index < 0 || index >= this.size) return -1; // 如果索引小于0或大于等于链表的长度，索引无效，返回 -1。// 2. 遍历链表到达目标索引let current = this.dummyHead.next; // 从链表的第一个实际节点开始（跳过虚拟头节点）for (let i = 0; i < index; i++) {current = current.next; // 逐个节点向前移动，直到达到目标索引的节点}// 3. 返回找到的节点的值return current.val; // 返回目标节点的值
}

临时指针指向头部节点，不是虚拟节点

2头部插入节点

第n个节点前插入节点（在头部插入节点的情况）

3.添加节点、删除节点要知道前一个节点，所以指针是指向虚拟节点的

添加节点

addAtIndex(index, val) {// 1. 检查索引的有效性if (index > this.size) return; // 如果索引大于链表的当前大小，插入操作是无效的，直接返回。// 2. 定位到要插入新节点位置的前一个节点let prev = this.dummyHead; // 从虚拟头节点开始for (let i = 0; i < index; i++) {prev = prev.next; // 移动到指定索引的前一个节点}// 3. 创建并插入新节点let newNode = new ListNode(val, prev.next); // 创建一个新节点，其 next 指向前一个节点的 nextprev.next = newNode; // 更新前一个节点的 next，使其指向新节点// 4. 更新链表大小this.size++; // 由于添加了一个新节点，链表的大小增加
}

删除第n个节点（极端情况节点只有一个的时候）

deleteAtIndex(index) {// 1. 检查索引的有效性if (index < 0 || index >= this.size) return; // 如果索引小于0或大于等于链表的长度，操作无效，直接返回。// 2. 找到要删除节点的前一个节点let prev = this.dummyHead; // 从虚拟头节点开始for (let i = 0; i < index; i++) {prev = prev.next; // 移动到指定索引的前一个节点}// 3. 删除指定索引的节点prev.next = prev.next.next; // 将前一个节点的 next 指向要删除节点的下一个节点，从而跳过了要删除的节点// 4. 更新链表的大小this.size--; // 因为删除了一个节点，所以链表的长度减少
}

要知道第n个节点的前面一个节点和后面一个节点

单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用

感想

心情很复杂，一个下午了居然就理解一道题

1.大概是要弄懂虚拟节点和指针的指向

2.目前的理解是，我们如果是需要添加或者删除节点，我们需要知道前一个节点是什么

3.我们需要找一个值，应该将我们现有的指针指向虚拟节点

4.读题比题目本身更加需要耐心，其实就是的要有耐心

5.长沙为什么那么冷啊，我的手啊好冷5555555~