算法巡练day03Leetcode203移除链表元素707设计链表206反转链表

今日学习的文章视频链接

https://www.bilibili.com/video/BV1nB4y1i7eL/?vd_source=8272bd48fee17396a4a1746c256ab0ae

https://programmercarl.com/0707.%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

链表理论基础

见我的博客 https://blog.csdn.net/qq_36372352/article/details/135322498

203 移除链表元素

题目描述

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

示例 1：

输入：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
输出：[]

提示：

列表中的节点数目在范围 [0, 104] 内
1 <= Node.val <= 50
0 <= val <= 50

两种方法

直接使用原来的链表来进行删除操作。

设置一个虚拟头结点在进行删除操作。

初学为了不把自己弄晕，只研究虚拟头节点的方法。

在这里插入图片描述

return 头结点的时候，别忘了 return dummyNode->next;， 这才是新的头结点

我遇到的困难

删除节点的循环中缺少了对 cur 指针的更新，这将导致无限循环。不删除节点时，应该更新 cur 到下一个节点。

完整代码，这里演示我的acm模式

#include <iostream>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x):val(x), next(nullptr) {}
    ListNode(int x, ListNode* next):val(x), next(next) {}
};

class Solution {
public:
    ListNode* removeElement(ListNode* head, int val) {
        ListNode* dummyNode = new ListNode(0);
        dummyNode->next = head;
        ListNode* cur = dummyNode;
        while (cur->next != nullptr) {
            if (cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            }
            else {
                cur = cur->next;
            }
        }
        head = dummyNode->next;
        delete dummyNode;
        return head;
    }
};

int main() {
    // 创建链表：1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6
    ListNode* head = new ListNode(1, new ListNode(2, new ListNode(6, 
                        new ListNode(3, new ListNode(4, new ListNode(5, 
                        new ListNode(6)))))));

    Solution solution;
    head = solution.removeElement(head, 6); // 移除所有值为 6 的节点

    // 打印更新后的链表
    ListNode* current = head;
    while (current != nullptr) {
        std::cout << current->val << " ";
        current = current->next;
    }
    std::cout << std::endl;

    // 释放链表占用的内存
    while (head != nullptr) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }

    return 0;
}

代码分析

if (cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            }

中tmp的意义

在这段代码中，定义 tmp 变量是为了正确地删除链表中的节点，同时保证链表的完整性和避免内存泄漏。让我们详细分析一下：

  1. 维护链表完整性:

    • cur->next 是当前要删除的节点。
    • 当你直接从链表中删除一个节点时（例如，通过 cur->next = cur->next->next;），你会丢失对当前节点的引用。如果没有 tmp 变量保存这个引用，你将无法访问并正确删除这个节点。

  2. 安全删除节点:

    • delete tmp; 是用来释放 tmp 所指向的节点（即原来的 cur->next）占用的内存。
    • 如果不使用 tmp 变量，而直接调用 delete cur->next;，就会在调用 cur->next = cur->next->next; 后尝试访问一个已经被删除的节点。这将导致未定义行为，可能是访问非法内存或程序崩溃。

  3. 保持链表的连接:

    • 在删除节点后，我们需要保证链表的其他部分仍然连接。这通过 cur->next = cur->next->next; 实现，它将当前节点的 next 指针指向要删除节点的下一个节点。
    • tmp 在这里充当一个临时桥梁，确保在删除节点和重新连接链表的过程中不会丢失任何节点。

综上所述，tmp 变量在删除链表节点的过程中发挥着重要的作用，既确保了链表结构的完整性，又避免了潜在的内存泄漏问题。

设计链表

题目描述

你可以选择使用单链表或者双链表，设计并实现自己的链表。

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

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类：

MyLinkedList() 初始化 MyLinkedList 对象。

int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。

void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。

void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。

void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。

void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

示例：

输入

[“MyLinkedList”, “addAtHead”, “addAtTail”, “addAtIndex”, “get”, “deleteAtIndex”, “get”]

[[], [1], [3], [1, 2], [1], [1], [1]]

输出

[null, null, null, null, 2, null, 3]

解释

MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3
myLinkedList.get(1);              // 返回 2
myLinkedList.deleteAtIndex(1);    // 现在，链表变为 1->3
myLinkedList.get(1);              // 返回 3

提示：

0 <= index, val <= 1000
请不要使用内置的 LinkedList 库。
调用 get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 的次数不超过 2000 。

我遇到的问题

添加在头节点前新增节点时不需要定义cur

在遍历节点过程中进行了_size++

//delete命令指示释放了tmp指针原本所指的那部分内存，
//被delete后的指针tmp的值（地址）并非就是NULL，而是随机值。也就是被delete后，
//如果不再加上一句tmp=nullptr,tmp会成为乱指的野指针
//如果之后的程序不小心使用了tmp，会指向难以预想的内存空间

   void deleteAtIndex(int index) {
        if (index < 0 || index > (_size - 1)) {
            return;
        }
        else {
            ListNode* cur = _dummyHead;
            while (index --) {
                cur = cur->next;
            }
            ListNode* tmp = cur->next;
            cur->next = cur->next->next;
            
            delete tmp;
            tmp=nullptr;
            _size--;
        }
    }

我的完整代码acm模式

# include <iostream>

class MyLinkList {
public:
    //定义链表
    struct ListNode {
        int val;
        ListNode *next = nullptr;
        ListNode(int x):val(x), next(nullptr) {}
    };

    MyLinkList() {
        _dummyHead = new ListNode(0);
        _size = 0;
        
    }

    int get(int index) {
        ListNode* cur = _dummyHead->next; 
        if (index < 0 || index > (_size - 1)) {
            return -1;
        }
       
        while (index--) {
            cur = cur->next;
        }
        return cur->val;

       
    }

    void addAtHead (int val) {
        // ListNode* cur = _dummyHead->next; 不需要cur指针
        ListNode* newNode = new ListNode(val);
        newNode->next = _dummyHead->next;
        _dummyHead->next = newNode;
        _size ++;
    }

    void addAtTail(int val) {
        ListNode* cur = _dummyHead;
        ListNode* newNode = new ListNode(val);
        while (cur->next != nullptr) {
            cur = cur->next;
        }
        cur->next = newNode;
        _size ++;
    }

    void addAtIndex(int index, int val) {
        if (index < 0 || index > _size) {
            return;
        }
        else {
            ListNode* cur = _dummyHead;
            while (index--) {  
                cur = cur->next;
            }
            ListNode* newNode = new ListNode(val);
            newNode->next = cur->next;
            cur->next = newNode;
            _size ++;
            
        }
    }

    void deleteAtIndex(int index) {
        if (index < 0 || index > (_size - 1)) {
            return;
        }
        else {
            ListNode* cur = _dummyHead;
            while (index --) {
                cur = cur->next;
            }
            ListNode* tmp = cur->next;
            cur->next = cur->next->next;
            
            delete tmp;
            tmp=nullptr;
            _size--;
        }
    }

    void printListNode() {
        ListNode* cur = _dummyHead;
        while (cur->next != nullptr) {
            std::cout << cur->next->val << " ";
            cur  = cur->next;
        }
        std::cout << std::endl;
    }

private:
    int _size;
    ListNode* _dummyHead;

};


int main() {
    MyLinkList myList;

    // Add elements to the list
    myList.addAtHead(1);
    myList.addAtTail(2);
    myList.addAtTail(3);
    myList.addAtIndex(1, 4);  // Add 4 at index 1

    // Print the current list
    std::cout << "Current List: ";
    myList.printListNode();

    // Get and print an element
    std::cout << "Element at index 2: " << myList.get(2) << std::endl;

    // Delete an element
    myList.deleteAtIndex(1);

    // Print the list after deletion
    std::cout << "List after deletion: ";
    myList.printListNode();

    return 0;
}

206反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

输入：head = [1,2,3,4,5]

输出：[5,4,3,2,1]

输入：head = [1,2]

输出：[2,1]

示例 3：

输入：head = []

输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

题目分析

反转链表遍历需要比一般的遍历多走一个节点，到Null，故终止条件为while(cur != nullptr),而不是while(cur->next != nullptr)

如果再定义一个新的链表，实现链表元素的反转，其实这是对内存空间的浪费。

其实只需要改变链表的next指针的指向，直接将链表反转 ，而不用重新定义一个新的链表，如图所示:
在这里插入图片描述

首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。

然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。

为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。

接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。

最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。 此时我们return pre指针就可以了，pre指针就指向了新的头结点。

我遇到的困难

多定义了一个虚拟头节点，导致反转后最后多输出了一个0

 // ListNode* dummyHead = new ListNode(0);
        // dummyHead->next = head;

我的acm模式完整代码

#include <iostream>
#include <vector>

struct ListNode {
    int val;
    ListNode* next = nullptr;
    ListNode(int x):val(x), next(nullptr) {}
    ListNode(int x, ListNode *next):val(x), next(next) {}
};

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *tmp;
        // ListNode* dummyHead = new ListNode(0);
        // dummyHead->next = head;
        ListNode* cur = head;
        ListNode* pre = nullptr;
        while (cur != nullptr) {
            tmp = cur->next;
            cur->next = pre; //翻转操作
            //更新pre和cur指针
            pre = cur;
            cur = tmp;
        }
        return pre;

    }

// 辅助函数，用于创建一个链表
ListNode* createList(const std::vector<int>& values) {
    ListNode* dummyHead = new ListNode(0);
    ListNode* cur = dummyHead;
    for (int value : values) {
        cur->next = new ListNode(value);
        cur = cur->next;
    }
    ListNode* head = dummyHead->next;
    delete dummyHead;
    return head;
}

// 辅助函数，用于打印链表
void printList(ListNode* head) {
    ListNode* cur = head;
    while (cur != nullptr) {
        std::cout << cur->val << " ";
        cur = cur->next;
    }
    std::cout << std::endl;
}
};

int main() {
    Solution sol;
    // 创建链表
    std::vector<int> values = {1, 2, 3, 4, 5};
    ListNode* head = sol.createList(values);

    // 打印原始链表
    std::cout << "Original List: ";
    sol.printList(head);

    // 反转链表
   
    ListNode* reversedHead = sol.reverseList(head);

    // 打印反转后的链表
    std::cout << "Reversed List: ";
    sol.printList(reversedHead);

    return 0;
}

        cur = cur->next;
    }
    std::cout << std::endl;
}
};

int main() {
    Solution sol;
    // 创建链表
    std::vector<int> values = {1, 2, 3, 4, 5};
    ListNode* head = sol.createList(values);

    // 打印原始链表
    std::cout << "Original List: ";
    sol.printList(head);

    // 反转链表
   
    ListNode* reversedHead = sol.reverseList(head);

    // 打印反转后的链表
    std::cout << "Reversed List: ";
    sol.printList(reversedHead);

    return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/286618.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Linux 命令echo

Linux 命令echo

命令作用 输出一行字符串在shell中&#xff0c;可以打印变量的值输出结果写入到文件在显示器上显示一段文字&#xff0c;起到提示的作用 语法 echo [选项] [字符串] 参数 字符含义-n不自动换行-e解释转义字符-E不解释转义字符 如果-e有效&#xff0c;则识别以下序列&…
阅读更多...
2024，这将是量子计算的真正挑战

2024，这将是量子计算的真正挑战

2023年&#xff0c;一项项量子计算纪录被打破。 谷歌量子AI团队证明了将多个量子比特分组合成为一个逻辑量子比特的纠错方法可以提供更低的容错率。以往的纠错研究随着比特数的增加&#xff0c;错误率会提高&#xff0c;都是“越纠越错”&#xff0c;而这次谷歌首次实现了“越纠…
阅读更多...
K8S本地开发环境-minikube安装部署及实践

K8S本地开发环境-minikube安装部署及实践

引言 在上一篇介绍了k8s的入门和实战&#xff0c;本章就来介绍一下在windows环境如何使用minikube搭建K8s集群&#xff0c;好了废话不多说&#xff0c;下面就和我一起了解Minikube吧。 什么是Minikube&#xff1f; Minikube 是一种轻量级的 Kubernetes 实现&#xff0c;可在本…
阅读更多...
1688商品详情API：实现商品详情自动化的关键步骤

1688商品详情API：实现商品详情自动化的关键步骤

一、准备工作 在使用1688商品详情API之前&#xff0c;我们需要进行一些准备工作。 注册与登录&#xff1a;首先&#xff0c;你需要在1688的开放平台上注册一个账号并创建一个应用。这样你就可以获得一个API密钥&#xff0c;这是调用API的凭证。阅读API文档&#xff1a;详细阅…
阅读更多...
web开发-springboot-web

web开发-springboot-web

报错&#xff1a; Failure to find org.springframework.boot:spring-boot-starter-parent:pom:3.2.1.RELEASE in https://maven.aliyun.com/nexus/content/groups/public was cached in the local repository, resolution will not be reattempted until the update interval …
阅读更多...
定制自己的GPTs，及使用ChatGPT/GPT4写程序的注意事项

定制自己的GPTs，及使用ChatGPT/GPT4写程序的注意事项

如何能高效地处理文本、文献查阅、PPT编辑、编程、绘图和论文写作已经成为您成功的关键。而 ChatGPT&#xff0c;作为一种强大的自然语言处理模型&#xff0c;具备显著优势&#xff0c;能够帮助您在各个领域取得突破。 ChatGPT 在论文写作与编程方面也具备强大的能力。无论是进…
阅读更多...
安卓在SOA中的运用

安卓在SOA中的运用

安卓在运用SOA研发的过程中&#xff0c;会针对实际情况对研发的架构和流程进行优化&#xff0c;通过优化过的架构和实施方案&#xff0c;不仅可以大大提升了整车开发的效率和灵活行以及功能落地的稳定性&#xff0c;同时也增加了系统的向上兼容性。 目前基于车载SOA系统的研发…
阅读更多...
记一个CSS样式实现思路（鼠标聚焦时完整内容，失焦时只显示部分）

记一个CSS样式实现思路（鼠标聚焦时完整内容，失焦时只显示部分）

效果图 默认状态 鼠标悬浮时 缓慢展示完整内容 实现方法 方法一 使用max-width,当鼠标悬浮时&#xff0c;设置max-width为一个足够大的数值 <div class"flex justify-center align-center mt-20px"><div v-for"(item, key) in ssoList" :key&q…
阅读更多...
HTML----JavaScript操作对象BOM对象

HTML----JavaScript操作对象BOM对象

文章目录 前言一、pandas是什么&#xff1f;二、使用步骤 1.引入库2.读入数据总结 本章要求 了解BOM模型掌握BOM模型实际应用 一.BOM模型概述 BOM&#xff08;浏览器对象模型&#xff09;是JavaScript中的一个重要概念&#xff0c;它提供了一组用于控制浏览器窗口和页面内容的…
阅读更多...
基于 ESP32-C3 开启 Flash 加密和安全启动并进行 OTA 测试

基于 ESP32-C3 开启 Flash 加密和安全启动并进行 OTA 测试

软件&#xff1a; esp-idf v5.1.2 硬件&#xff1a; ESP32-C3 board 1. 首先&#xff0c;准备一个明文固件 hello-world.bin 基于 esp-idf-v5.1.2\examples\get-started\hello_world 例程&#xff0c;使用如下指令&#xff0c;直接编译&#xff0c;获取明文固件 hello-worl…
阅读更多...
大数据时代快速获取数据方法，爬虫技术理论剖析与实战演练

大数据时代快速获取数据方法，爬虫技术理论剖析与实战演练

一、教程描述 人工智能和机器学习&#xff0c;都离不开数据&#xff0c;若是没有数据&#xff0c;再好的算法&#xff0c;再好的模型&#xff0c;都没有用武之地。数据不仅是指现成的数据库&#xff0c;更加是指每天增加的海量互联网数据。本套教程将通过多个实战项目&#xf…
阅读更多...
2024上海国际智慧城市,物联网,大数据博览会（上海智博会）

2024上海国际智慧城市,物联网,大数据博览会（上海智博会）

随着科技的飞速发展&#xff0c;智慧城市、物联网与大数据已经成为当今社会发展的重要驱动力。作为国内最具影响力的科技展会之一&#xff0c;2024上海国际智慧城市,物联网,大数据博览会&#xff08;简称:世亚智博会&#xff09;汇聚了全球顶尖的智慧城市、物联网与大数据技术&…
阅读更多...
JMeter之测试WebService接口

JMeter之测试WebService接口

JMeter之测试WebService接口 1 背景2 目的3 介绍4 具体操作4.1 soapUI调用4.2 JMeter工具调用4.3 操作步骤流程4.3 重点 1 背景 WebService应用的范围是非常广&#xff0c;任何需要跨平台、跨系统进行数据交换和功能调用的场景都可以用此来实现&#xff0c;在实际的工作中也常常…
阅读更多...
k8s-yaml格式

k8s-yaml格式

三种常见的项目发布方式&#xff1a; 蓝绿发布&#xff1a; 金丝雀发布&#xff08;灰度发布&#xff09;&#xff1a; 滚动发布&#xff1a; 应用程序升级&#xff0c;面临的最大的问题&#xff0c;就是新旧业务的更换&#xff0c;立项--定稿--需求发布--开发--测试--发布&…
阅读更多...
有效边表填充算法

有效边表填充算法

有效边表填充算法 如何填充示例三角形 按照扫描线从上往下的顺序&#xff0c;依次处理和多边形相交的扫描线&#xff0c;对于当前处理的扫描线找到和它相交的所有边的交点&#xff0c;按照交点横坐标从小到大的顺序&#xff0c;两个两个配对&#xff0c;配对之后填充每对交点之…
阅读更多...
踩了Vue2运行机制的坑-响应式原理

踩了Vue2运行机制的坑-响应式原理

最近遇到一个很奇怪的bug&#xff1a; 前置&#xff1a;后端接口返回的数据是这样的&#xff1a; ①首先在store中取出后端返回的数据Ares.data&#xff0c;在这里打印输出是正常的 ②然后在vue页面上再取出A.data也就是res.data.data&#xff0c;以及其它几个字段即res.data.X…
阅读更多...
Spring技术内幕笔记之IOC的实现

Spring技术内幕笔记之IOC的实现

IOC容器的实现 依赖反转&#xff1a; 依赖对象的获得被反转了&#xff0c;于是依赖反转更名为&#xff1a;依赖注入。许多应用都是由两个或者多个类通过彼此的合作来实现业务逻辑的&#xff0c;这使得每个对象都需要与其合作的对象的引用&#xff0c;如果这个获取过程需要自身…
阅读更多...
解决报错：找不到显卡

解决报错：找不到显卡

今天做实验碰到一个问题&#xff1a;torch找不到显卡&#xff1a; 打开任务管理器&#xff0c;独显直接没了&#xff0c;一度以为是要去修电脑了&#xff0c;突然想到上次做实验爆显存&#xff0c;屏蔽了gpu用cpu训练&#xff1a; import os os.environ["CUDA_DEVICE_OR…
阅读更多...
线性代数笔记3 1.1

线性代数笔记3 1.1

学习视频&#xff1a; 2.2 矩阵运算&#xff08;二&#xff09;_哔哩哔哩_bilibili 包括内容&#xff1a; p10矩阵运算&#xff08;二&#xff09; p11特殊矩阵 p12逆矩阵&#xff08;一&#xff09; p13逆矩阵&#xff08;二&#xff09;
阅读更多...
网络四元组

网络四元组

文章目录 网络四元组 今天我们来聊聊 网络四元组 网络四元组 四元组&#xff0c;简单理解就是在 TCP 协议中&#xff0c;去确定一个客户端连接的组成要素&#xff0c;它包括源 IP 地址、目标 IP 地址、源端口号、目标端口号。 正常情况下&#xff0c;我们对于网络通信的认识可…
阅读更多...
最新文章

Copyright @ 2022~2023