首页 > 其他分享 >链表part01

链表part01

时间:2024-08-03 21:18:19浏览次数:17  
标签:index cur val part01 next 链表 int

今天是8月2日,学习了链表的基础知识。题目主要是链表的基础操作和反转链表,注意虚拟头节点的使用、next的顺序和tmp的灵活使用。

1. 移除元素

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


  1. 删除的方法,cur指针挨个遍历,若是cur->next和val同,则删除cur->next。(所以,while中的判断条件是cur->next不为null,因为比较和删除的都是cur->next)。
  2. 若是删除第一个不方便,所以加一个虚拟头节点。
  1. 注意C++中开辟空间的方法。
  2. 注意设置指针的方法,二者有何区别。
ListNode* removeElements(ListNode* head, int val) {
    // 设置一个虚拟头结点 ListNode(int x) : val(x), next(nullptr) {}
    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. 707 设计链表

题目:实现 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 的节点。

思路:

  1. 注意头节点的运用。
  2. 注意C++中构造函数的写法。(先在外头写一个struct
  3. 注意每个函数进去先判断特殊情况,例如index<0||index>=size
  4. 注意再往后顺链表时的截至条件。
  5. 足以delete时释放空间的写法。
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>0){ // 如果--index 就会陷入死循环
            cur = cur->next;
            index--;
        }
        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++;
    }

    // 头插入
    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++;
    }

    // 删除第index个节点,如果index 大于等于链表的长度,直接return,注意index是从0开始的
    void deleteAtIndex(int index) {
        if (index >= _size || index < 0) {
            return;
        }
        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--;
    }

    // 打印链表
    void printLinkedList() {
        LinkedNode* cur = _dummyHead;
        while (cur->next != nullptr) {
            cout << cur->next->val << " ";
            cur = cur->next;
        }
        cout << endl;
    }
private:
    int _size;
    LinkedNode* _dummyHead;

};

3. 反转链表(双指针+临时变量)

题目:给单链表的头节点 head ,返回反转后的链表。


最直接的想法就是把next的指针调转方向,但是一个指针一定做不到,所以需要双指针precur。想一想即可知,cur的next指向pre之后,到不了cur的下一个了,所以解决办法:提前存下cur的下一个的位置,即设置一个tmp指针指向cur->next

ListNode* reverseList(ListNode* head) {
    ListNode* cur = head;
    ListNode* pre = nullptr;
    while(cur!=nullptr){
        ListNode* tmp = cur->next;
        cur->next = pre;
        pre = cur;
        cur = tmp;
    }
    return pre;
}

今日古诗

乌夜啼·纨扇婵娟素月

陆游〔宋代〕

纨扇婵娟素月,纱巾缥缈轻烟。高槐叶长阴初合,清润雨馀天。
弄笔斜行小草,钩帘浅醉闲眠。更无一点尘埃到,枕上听新蝉。

标签:index,cur,val,part01,next,链表,int
From: https://www.cnblogs.com/yuehuaicnblogs/p/18341106

相关文章

  • 结构体与共用体,链表的学习
    结构体定义        C语言允许用户自己定义一种数据结构,称为结构体。        声明一个结构体类型一般形式为:                strcut 结构体名                {                    成员列表......
  • 141.环形链表
    给你一个链表的头节点 head ,判断链表中是否有环。如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从0开始)。注意:pos 不作为参数进行传递 。仅仅是为......
  • LeetCode | 单链表操作
    LeetCode203移除链表元素LeetCode707设计链表LeetCode206反转链表主类ListNodepackagecom.github.dolphinmind.linkedlist.uitls;/***@authordolphinmind*@ClassNameListNode*@description*@date2024/8/3*///链表组成元素:节点publicclass......
  • 信友队集训营--1--链表
    算法随笔(1):信友队集训营--1--链表链表单向链表计算机常见的两种存储结构分别是顺序存储和链式存储顺序存储(以数组方式呈现)优点有:操作方便,随机存取,查找元素的时间复杂度为O(1)缺点有:需要预设空间,过大浪费,过小越界。插入或删除元素不方便,需要O(N)的复杂度链式存储(以链表方式呈现)......
  • Python数据结构第二天—循环链表、树、二叉搜索树
    双向链表之前学习的单向链表只能从头遍历到尾,过程是单向的,而双向链表既可以从头遍历到尾,也可以从尾遍历到头,它的过程是双向的。既然它是双向的,那么我们要实现一个双向链表,就需要在单向链表的基础上,给每一个结点增加一个向前的引用。双向链表的创建:"""我们要实现的是一......
  • 链表尾插法、头删、尾删,共用体、位运算。
    一、链表1、尾插程序:2、头删3、尾删4、清空链表二、共用体1、定义:union 共用体名(首字母大写。所占字节大小:结构体变量所占内存长度是各成员占的内存长度之和。每个成员分别占有其自己的内存单元。共用体变量所占的内存长度等于最长的成员的长度。但是整体大......
  • c语言结构体的概述,定义结构体变量类型的方法,结构体变量的引用,结构体变量的初始化,结构
    1.C语言结构体的概述在C语言中,结构体(struct)是一种复合数据类型,用于将不同类型的数据组合在一起。它可以包含基本数据类型(如int、float、char等)以及其他结构体。结构体非常适合表示具有多种属性的复杂数据,如学生信息(包含姓名、年龄、成绩等)或坐标点(包含x和y坐标)。结构......
  • 【数据结构算法经典题目刨析(c语言)】判断链表是否有环(图文详解)
    ......
  • 数据结构: 单向链表
    目录一、链表的概念及结构二、单链表的实现2.1头文件2.2各个功能的实现2.2.1内存申请 2.2.2头插,尾插,头删,尾删头插 尾插 头删尾删 2.2.3查找数据 2.2.4指定位置前中后的数据增删指定位置之前插入数据指定位置之后插入数据删除指定位置之后数据删......
  • 双向链表的实现
    1、双向链表示意图 2、双向链表实现(1)结构体定义typedefintLTDataType;typedefstructListNode{ LTDataTypedata; structListNode*prev; structListNode*next; }LTNode;(2)初始化/****************初始化*****************/LTNode*ListInit(LTNode*phead......