【12.24】转行小白历险记-刷算法03

2023-12-24 22:49:57

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

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

一、链表

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;
};

代码解释

  1. 删除头节点:

    • 使用 while 循环检查头节点是否需要删除(即头节点的值等于 val)。
    • 如果需要删除,将头节点更新为下一个节点。
  2. 删除非头节点:

    • 使用另一个 while 循环遍历链表。
    • let cur = head; 这一步是为了在不改变头节点引用的前提下遍历和操作链表
    • 如果当前节点的下一个节点的值等于 val,则删除该节点。
  3. 返回头节点:

    • 在删除操作完成后,返回更新后的头节点。

回顾一下while和if的区别

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

if 语句

  1. 用途if 语句用于基于特定条件执行一段代码。如果该条件为真(true),则执行 if 块内的代码;如果为假(false),则跳过该代码块。

  2. 一次性检查if 语句仅在条件首次评估时检查一次。不论条件之后如何变化,if 块内的代码只会基于最初的条件检查被执行或跳过。

while 循环

  1. 用途while 循环用于在条件为真时重复执行代码块。只要条件保持为真,循环就会继续进行。

  2. 重复检查:在 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 指向前一个节点的 next
    prev.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~

?

文章来源:https://blog.csdn.net/TTTT2222111/article/details/135181325
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。