【Leetcode】 707. 设计链表

2023-10-18 19:28
文章标签 leetcode 设计 链表 707

本文主要是介绍【Leetcode】 707. 设计链表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

单链表中的节点应该具备两个属性valnextval当前节点的值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 库。
调用 getaddAtHeadaddAtTailaddAtIndexdeleteAtIndex 的次数不超过 2000


AC:

/** @lc app=leetcode.cn id=707 lang=cpp** [707] 设计链表*//*** Your MyLinkedList object will be instantiated and called as such:* MyLinkedList* obj = new MyLinkedList();* int param_1 = obj->get(index);* obj->addAtHead(val);* obj->addAtTail(val);* obj->addAtIndex(index,val);* obj->deleteAtIndex(index);*/
// @lc code=start
class MyLinkedList {
public:struct LinkNode {int val;LinkNode* next;LinkNode(int val):val(val), next(nullptr){}};MyLinkedList() {_dummyHead = new LinkNode(0);_size = 0;}int get(int index) {if(index > (_size - 1) || (index < 0)) {return -1;}LinkNode* cur = _dummyHead->next;while(index--) {cur = cur->next;}return cur->val;}void addAtHead(int val) {LinkNode* newNode = new LinkNode(val);newNode->next = _dummyHead->next;_dummyHead->next = newNode;_size++;}void addAtTail(int val) {LinkNode* newNode = new LinkNode(val);LinkNode* cur = _dummyHead;while(cur->next) {cur = cur->next;}cur->next = newNode;_size++;}void addAtIndex(int index, int val) {if(index > _size)return ;if(index < 0)index = 0;LinkNode* newNode = new LinkNode(val);LinkNode* cur = _dummyHead;while(index--) {cur = cur->next;}newNode->next = cur->next;cur->next = newNode;_size++;}void deleteAtIndex(int index) {if(index >= _size || index < 0)return ;LinkNode* cur = _dummyHead;while(index--) {cur = cur->next;}LinkNode* tmp = cur->next;cur->next = cur->next->next;tmp = nullptr;delete(tmp);_size--;}
private:int _size;LinkNode* _dummyHead;
};
// @lc code=end

AC

需要注意的是,链表初始化时出现的c++11 构造函数与成员初始化器列表语法
C++11引入了新的成员初始化器列表语法,可以更方便地初始化成员变量。使用该语法的构造函数的函数体之前,必须有一个成员初始化器列表,用冒号(:)分隔。初始化器列表的语法如下:

class MyClass {
public:// 无参构造函数MyClass() : member1(initialValue1), member2(initialValue2), ... {// 构造函数体}// 有参构造函数MyClass(int arg1, double arg2, ...) : member1(arg1), member2(arg2), ... {// 构造函数体}private:// 成员变量int member1;double member2;...
};

其中,initialValue1initialValue2等为成员变量的初始值,arg1arg2等为构造函数的参数。在成员初始化器列表中,每一个成员变量的初始化语句使用逗号分隔,每个语句由成员变量名称和初始化表达式组成(也可以使用成员函数返回值进行初始化)。对于没有在初始化器列表中出现的成员变量,它们会使用它们的默认构造函数进行初始化。

使用成员初始化器列表可以减少代码行数内存分配次数,提高程序的效率和可读性。


假设有一个类 Person,包含了名字(name)、年龄(age)、职业(job)等成员变量,我们可以使用成员初始化器列表来初始化这些成员变量:

class Person {
public:// 有参构造函数Person(string _name, int _age, string _job) : name(_name), age(_age), job(_job){// 构造函数体}private:string name;int age;string job;
};

在上面的代码中,我们使用了成员初始化器列表来初始化 nameagejob 这三个成员变量,代码更加简洁高效。

如果不使用成员初始化器列表,代码如下:

class Person {
public:// 有参构造函数Person(string _name, int _age, string _job) {name = _name;age = _age;job = _job;// 构造函数体}private:string name;int age;string job;
};

这样的代码虽然跟使用成员初始化器列表的代码基本相同,但是在代码实际执行的时候,由于需要对成员变量进行多次赋值,所以效率会低一些。因此,在实际开发中推荐使用成员初始化器列表

这篇关于【Leetcode】 707. 设计链表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/234665

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

csu1329(双向链表)

题意:给n个盒子,编号为1到n,四个操作:1、将x盒子移到y的左边;2、将x盒子移到y的右边;3、交换x和y盒子的位置;4、将所有的盒子反过来放。 思路分析:用双向链表解决。每个操作的时间复杂度为O(1),用数组来模拟链表,下面的代码是参考刘老师的标程写的。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#

怎么让1台电脑共享给7人同时流畅设计

在当今的创意设计与数字内容生产领域,图形工作站以其强大的计算能力、专业的图形处理能力和稳定的系统性能,成为了众多设计师、动画师、视频编辑师等创意工作者的必备工具。 设计团队面临资源有限,比如只有一台高性能电脑时,如何高效地让七人同时流畅地进行设计工作,便成为了一个亟待解决的问题。 一、硬件升级与配置 1.高性能处理器(CPU):选择多核、高线程的处理器,例如Intel的至强系列或AMD的Ry

深入手撕链表

链表 分类概念单链表增尾插头插插入 删尾删头删删除 查完整实现带头不带头 双向链表初始化增尾插头插插入 删查完整代码 数组 分类 #mermaid-svg-qKD178fTiiaYeKjl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-

基于51单片机的自动转向修复系统的设计与实现

文章目录 前言资料获取设计介绍功能介绍设计清单具体实现截图参考文献设计获取 前言 💗博主介绍:✌全网粉丝10W+,CSDN特邀作者、博客专家、CSDN新星计划导师,一名热衷于单片机技术探索与分享的博主、专注于 精通51/STM32/MSP430/AVR等单片机设计 主要对象是咱们电子相关专业的大学生,希望您们都共创辉煌!✌💗 👇🏻 精彩专栏 推荐订阅👇🏻 单片机

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

建立升序链表

题目1181:遍历链表 时间限制:1 秒 内存限制:32 兆 特殊判题:否 提交:2744 解决:1186 题目描述: 建立一个升序链表并遍历输出。 输入: 输入的每个案例中第一行包括1个整数:n(1<=n<=1000),接下来的一行包括n个整数。 输出: 可能有多组测试数据,对于每组数据, 将n个整数建立升序链表,之后遍历链表并输出。 样例输

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &