首页 > 其他分享 >代码随想录(Day 3)

代码随想录(Day 3)

时间：2024-04-07 18:58:06浏览次数：18  
标签：index cur val 代码 随想录 next 链表 节点 Day

今日任务
1.移除链表元素
2.设计链表
3.翻转链表

1.移除链表元素

LeetCode链接

链表经典操作，对于原理不过多解释，主要探讨建立虚拟头结点和不建立虚拟头结点的区别。

对于链表操作时，大多数参考书上都给出头结点不需要带数据，这样做是有道理的。
因为在链表中，我们涉及到链表的操作时，除了改变结点指针指向就是删除与增加结点了。

而我们在删除结点时，对于链表中部结点，几乎都能联想到3个结点之间的操作，无非就是第1个结点通过指针指向第3个结点，再free掉第二个结点。
而到链表首结点时，只有首结点和次结点了，有时候容易忘记操作，无非就是再引入一个虚拟头结点，并将head对其赋值，然后free掉虚拟头结点再使head往后移就行了。

所以，我们为什么不直接在一开始就引入一个头结点呢，使得头结点后面next真正的头结点，最后return dummynode->next；就行了，给出代码

这是不带头结点

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        while (head != NULL && head->val == val) { 
            ListNode* tmp = head;
            head = head->next;
            delete tmp;
        }
        ListNode* cur = head;
        while (cur != NULL && cur->next!= NULL) {
            if (cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            } else {
                cur = cur->next;
            }
        }
        return head;
    }
};

这是带头结点

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

2.设计链表

LeetCode链接

题意

  • get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
  • addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
  • addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
  • addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
  • deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

此题目我们主要来探讨主函数模式和主输入模式之间的相互转换

我个人在做题中发现，用惯了LeetCode的主函数模式刷题，而在面对ACM中的主输入模式后会很难下手。

首先我先贴出主输入模式的代码（较长）

先给出题目

输入数据只有一组，第一行有n+1个整数，第一个整数是这行余下的整数数目n，后面是n个整数。
这一行整数是用来初始化列表的，并且输入的顺序与列表中的顺序相反，也就是说如果列表中是1、2、3那么输入的顺序是3、2、1。（初始化链表的元素是倒序的，这个使用题目中创建列表的方法（从头部插入）就可以了。）
第二行有一个整数m，代表下面还有m行。每行有一个字符串，字符串是“get”，“insert”，“delete”，“show”中的一种。
如果是“get”，代表获得第a个元素。（a从1开始计数）
如果是“delete”，代表删除第a个元素。（a从1开始计数）
如果是“insert”，则其后跟着两个整数a和e，代表在第a个位置前面插入e。（a从1开始计数）
“show”之后没有正数，直接打印链表全部内容。

#include<iostream>
using namespace std;
// 定义链表节点结构体
struct LinkedNode {
    int val;
    LinkedNode* next;
    LinkedNode(int val):val(val), next(nullptr){}
};

int _size = 0;
LinkedNode* _dummyHead =  new LinkedNode(0); // 这里定义的头结点 是一个虚拟头结点，而不是真正的链表头结点

// 获取到第index个节点数值，如果index是非法数值直接返回-1， 注意index是从0开始的，第0个节点就是头结点
int get(int index) {
    if (index > (_size - 1) || index < 0) {
        return -1;
    }
    LinkedNode* cur = _dummyHead->next;
    while(index--){ // 如果--index 就会陷入死循环
        cur = cur->next;
    }
    return cur->val;
}

// 在链表最前面插入一个节点，插入完成后，新插入的节点为链表的新的头结点
void addAtHead(int val) {
    LinkedNode* newNode = new LinkedNode(val);
    newNode->next = _dummyHead->next;
    _dummyHead->next = newNode;
    _size++;
}

// 在链表最后面添加一个节点
void addAtTail(int val) {
    LinkedNode* newNode = new LinkedNode(val);
    LinkedNode* cur = _dummyHead;
    while(cur->next != nullptr){
        cur = cur->next;
    }
    cur->next = newNode;
    _size++;
}

// 在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
// 如果index 等于链表的长度，则说明是新插入的节点为链表的尾结点
// 如果index大于链表的长度，则返回空
// 如果index小于0，则在头部插入节点
int addAtIndex(int index, int val) {

    if(index > _size) return -1;
    if(index < 0) return -1;
    LinkedNode* newNode = new LinkedNode(val);
    LinkedNode* cur = _dummyHead;
    while(index--) {
        cur = cur->next;
    }
    newNode->next = cur->next;
    cur->next = newNode;
    _size++;
    return 0;
}

// 删除第index个节点，如果index 大于等于链表的长度，直接return，注意index是从0开始的
int deleteAtIndex(int index) {
    if (index >= _size || index < 0) {
        return -1;
    }
    LinkedNode* cur = _dummyHead;
    while(index--) {
        cur = cur ->next;
    }
    LinkedNode* tmp = cur->next;
    cur->next = cur->next->next;
    delete tmp;
    //delete命令指示释放了tmp指针原本所指的那部分内存，
    //被delete后的指针tmp的值（地址）并非就是NULL，而是随机值。也就是被delete后，
    //如果不再加上一句tmp=nullptr,tmp会成为乱指的野指针
    //如果之后的程序不小心使用了tmp，会指向难以预想的内存空间
    tmp=nullptr;
    _size--;
    return 0;
}

// 打印链表
int printLinkedList() {
    LinkedNode* cur = _dummyHead;
    if (cur->next == nullptr) return -1;
    while (cur->next != nullptr) {
        cout << cur->next->val << " ";
        cur = cur->next;
    }
    cout << endl;
    return 0;
}

int main() {
    int n, a, m, t, z;
    string s;
    cin >> n;
    LinkedNode* head = nullptr;
    while (n--) {
        cin >> a;
        addAtHead(a);
    }
    cin >> m;
    while (m--) {
        cin >> s;
        if (s == "show")  {
            if (printLinkedList() == -1) cout << "Link list is empty" << endl;
        }
        if (s == "delete") {
            cin >> t; 
            // 本题的删除索引是从1开始，函数实现是从0开始，所以这里是 t - 1
            if (deleteAtIndex(t - 1) == -1) cout << "delete fail" << endl; 
            else cout << "delete OK" << endl;
        }
        if (s == "insert") {
            cin >> t >> z; 
            if (addAtIndex(t - 1, z) == -1) cout << "insert fail" << endl;
            else cout << "insert OK" << endl;

        }
        if (s == "get") {
            cin >> t;
            int getValue = get(t - 1);
            if (getValue == -1) cout << "get fail" << endl;
            else cout << getValue << endl;
        }
    }
}

再给出主函数的代码

class MyLinkedList {
public:
    // 定义链表节点结构体
    struct LinkedNode {
        int val;
        LinkedNode* next;
        LinkedNode(int val):val(val), next(nullptr){}
    };

    // 初始化链表
    MyLinkedList() {
        _dummyHead = new LinkedNode(0); // 这里定义的头结点 是一个虚拟头结点，而不是真正的链表头结点
        _size = 0;
    }

    // 获取到第index个节点数值，如果index是非法数值直接返回-1， 注意index是从0开始的，第0个节点就是头结点
    int get(int index) {
        if (index > (_size - 1) || index < 0) {
            return -1;
        }
        LinkedNode* cur = _dummyHead->next;
        while(index--){ // 如果--index 就会陷入死循环
            cur = cur->next;
        }
        return cur->val;
    }

    // 在链表最前面插入一个节点，插入完成后，新插入的节点为链表的新的头结点
    void addAtHead(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        newNode->next = _dummyHead->next;
        _dummyHead->next = newNode;
        _size++;
    }

    // 在链表最后面添加一个节点
    void addAtTail(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = _dummyHead;
        while(cur->next != nullptr){
            cur = cur->next;
        }
        cur->next = newNode;
        _size++;
    }

    // 在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
    // 如果index 等于链表的长度，则说明是新插入的节点为链表的尾结点
    // 如果index大于链表的长度，则返回空
    // 如果index小于0，则在头部插入节点
    void addAtIndex(int index, int val) {

        if(index > _size) return;
        if(index < 0) index = 0;        
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = _dummyHead;
        while(index--) {
            cur = cur->next;
        }
        newNode->next = cur->next;
        cur->next = newNode;
        _size++;
    }

在这里我想把这两个代码之间的区别直接贴出来，不然太长串不好看

第一个区别，在主输入模式中， 变量是直接定义在全局下的

int _size = 0;
LinkedNode* _dummyHead =  new LinkedNode(0); // 这里定义的头结点 是一个虚拟头结点，而不是真正的链表头结点

而主函数模式下，变量是定义在private成员里面

private:
    int _size;
    LinkedNode* _dummyHead;

最重要的便是主输入模式下的主函数了

int main() {
    int n, a, m, t, z;
    string s;
    cin >> n;
    LinkedNode* head = nullptr;
    while (n--) {
        cin >> a;
        addAtHead(a);
    }
    cin >> m;
    while (m--) {
        cin >> s;
        if (s == "show")  {
            if (printLinkedList() == -1) cout << "Link list is empty" << endl;
        }
        if (s == "delete") {
            cin >> t; 
            // 本题的删除索引是从1开始，函数实现是从0开始，所以这里是 t - 1
            if (deleteAtIndex(t - 1) == -1) cout << "delete fail" << endl; 
            else cout << "delete OK" << endl;
        }
        if (s == "insert") {
            cin >> t >> z; 
            if (addAtIndex(t - 1, z) == -1) cout << "insert fail" << endl;
            else cout << "insert OK" << endl;

        }
        if (s == "get") {
            cin >> t;
            int getValue = get(t - 1);
            if (getValue == -1) cout << "get fail" << endl;
            else cout << getValue << endl;
        }
    }
}
  1. 首先，读取用户输入的整数 n，表示要插入到链表中的节点个数。
  2. 使用一个循环，读取 n 个整数 a，并调用 addAtHead(a) 将这些节点插入到链表的头部。
  3. 读取用户输入的整数 m，表示接下来要执行的命令个数。
  4. 使用一个循环，读取用户输入的命令 s，并根据命令执行相应的操作。
    • 如果命令是 "show"，调用 printLinkedList() 打印链表中的元素。
    • 如果命令是 "delete"，读取要删除的节点索引 t，调用 deleteAtIndex(t - 1) 删除对应索引的节点。
    • 如果命令是 "insert"，读取要插入的节点索引 t 和值 z，调用 addAtIndex(t - 1, z) 在对应索引之前插入新节点。
    • 如果命令是 "get"，读取要获取的节点索引 t，调用 get(t - 1) 获取对应索引的节点值。
  5. 执行完所有命令后，程序结束。

3.翻转链表（小重点） 

先给出图解

由这两张图我们就能很清晰的分析出了

1.首先先建立一个pre指针指向null
2.再为head头指针建立一个别名cur
3.别忘记用temp来临时保存一下cur的next位置

给出代码

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* temp; // 保存cur的下一个节点
        ListNode* cur = head;
        ListNode* pre = NULL;
        while(cur) {
            temp = cur->next;  // 保存一下 cur的下一个节点，因为接下来要改变cur->next
            cur->next = pre; // 翻转操作
            // 更新pre 和 cur指针
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

 

标签：index,cur,val,代码,随想录,next,链表,节点,Day
From： https://blog.csdn.net/vKohl/article/details/137438280

相关文章

  • csdn博客自定义模块：显示实时天气、日历、随机语录代码
    目录1.样式说明2.效果展示3.代码下载1.样式说明vip会员或者博客专家可以自定义模块代码，比如我博客的样式，有这几部分组成：灯笼祝福（我这里是龙年快乐，可以自定义更改任何字）、滚动欢迎语（我这里是欢迎访问我的博客，可以自定义更改任何欢迎语）github链接、知乎链接、邮箱发......
  • R语言Copula对债券时间序列数据的流动性风险进行度量|附代码数据
    全文链接：http://tecdat.cn/?p=32707原文出处：拓端数据部落公众号在金融市场中，债券的流动性风险一直是一个备受关注的问题。流动性风险是指在市场上，债券价格的波动程度受到市场流动性的影响，这种影响可能导致债券价格的剧烈波动，从而影响投资者的收益。因此，对于债券流动性风险的度量......
  • 身份证真伪查询接口、身份证实名认证一行python代码即可实现，实时数据
    互联网多元化的发展使得互联网金融、O2O、交友等新型商业形式不断的兴起与创新，也正因如此，互联网企业对于实名认证接口的需求也在不断的增多，对数据形式，可靠性也有了更高的需求，对此衍生了身份证实名认证接口业务，那么如何通过一行python代码来实现实名认证呢？以翔云身份证实......
  • day12-内置模块和开发规范
    1.内置模块1.1jsonjson模块，是python内部的一个模块，可以将python的数据格式转换为json格式的数据，也可以将json格式的数据转换为python的数据格式。json格式，是一个数据格式（本质上就是个字符串，常用语网络数据传输）#Python中的数据类型的格式data=[{"id":1,"name":"......
  • 顺序栈和链栈的部分功能完整代码
    一、顺序栈代码#include<iostream>#include<stdlib.h>usingnamespacestd;#defineOK1#defineERROR0#defineMAXSIZE100typedefintElemType;typedefintStatus;typedefstruct {   ElemType*elem;   inttop;}Sqstack;StatusInitStack(Sqsta......
  • 18天【代码随想录算法训练营34期】● 513.找树左下角的值 ● 112. 路径总和 113.路径
    513.找树左下角的值#Definitionforabinarytreenode.#classTreeNode:#def__init__(self,val=0,left=None,right=None):#self.val=val#self.left=left#self.right=rightclassSolution:deffindBottomLeftValue(self......
  • SAP 零代码完成批量导入功能
    最近项目被流程给烦的不行不行的，现在只要动代码就要走流程，走预算，是不是甲方都这样，我在Miniso怎没这样的感觉.所以发现认识逼出来，没有这样条条框框也就不会想更好解决办法，今天介绍一种小白导数据的办法，不需要代码经验，只要点三个按钮就能导入数据。              ......
  • 保护你的 Java 代码：深入了解代码混淆
    在当今数字化时代，软件开发领域竞争激烈，而保护你的代码免受恶意攻击和盗用是至关重要的。代码混淆是一种常用的技术，用于增加攻击者分析和逆向工程代码的难度，从而提高代码的安全性。本文将介绍代码混淆的基本概念和详细办法，帮助你保护Java代码的安全性。1.代码混淆简介代码......
  • java代码混淆,保护源码的重要性
    Java代码混淆是一种重要的安全措施，用于保护Java应用程序的源代码免受恶意攻击和逆向工程的影响。下面是关于Java代码混淆以及保护源码重要性的详细说明：1.什么是Java代码混淆？Java代码混淆是指通过对Java代码进行一系列的转换和优化，使得源代码变得难以理解和分析，从而增加攻击......
  • 代码手术刀—自定义你的代码重构工具
    前言笔者近日在做代码仓库的存量代码缩减工作，首先考虑的是基于静态扫描的缩减，尝试使用了很多工具来对代码进行优化，例如PMD、IDEA自带的inspect功能、findBugs等。但是无一例外，要么过于“保守”，只给出扫描结果，但是无法实现一键优化，要么直接就是有bug（这里特指IDEA2023.1.5专业版-in......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99