[每日 LeetCode] 707. Design Linked List

本贴最后更新于 2146 天前,其中的信息可能已经时移世异

Description:

Design your implementation of the linked list. You can choose to use the singly linked list or the doubly linked list. A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node. If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed.

Implement these functions in your linked list class:

  • get(index) : Get the value of the index -th node in the linked list. If the index is invalid, return -1.
  • addAtHead(val) : Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
  • addAtTail(val) : Append a node of value val to the last element of the linked list.
  • addAtIndex(index, val) : Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
  • deleteAtIndex(index) : Delete the index-th node in the linked list, if the index is valid.

Example:

MyLinkedList linkedList = new MyLinkedList(); linkedList.addAtHead(1); linkedList.addAtTail(3); linkedList.addAtIndex(1, 2); // linked list becomes 1->2->3 linkedList.get(1); // returns 2 linkedList.deleteAtIndex(1); // now the linked list is 1->3 linkedList.get(1);    // returns 3

Note:

  • All values will be in the range of [1, 1000].
  • The number of operations will be in the range of [1, 1000].
  • Please do not use the built-in LinkedList library.

思路:本题要求自己设计实现链表的基本操作,不能使用已有的模板函数,用双链表或者单链表均可。单链表处理起来稍微简单点,这里使用单链表进行操作,主要注意各个操作处理的细节,开始提交时忘记判断 index 小于 0 的情况,导致没有通过,加上这个判断就好了。


C++ 代码

class Node{ public: int val; Node* next; Node(int val){this->val = val; next = NULL;} }; class MyLinkedList { public: /** Initialize your data structure here. */ int size = 0; Node* head = new Node(0); MyLinkedList() { } /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */ int get(int index) { if (index >= size || index < 0) return -1; Node* temp = head->next; for(int i=0; i<index; i++) temp = temp->next; return temp->val; } /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */ void addAtHead(int val) { Node* temp = head->next; head->next = new Node(val); head->next->next = temp; size++; } /** Append a node of value val to the last element of the linked list. */ void addAtTail(int val) { Node* temp = head; while(temp->next != NULL) temp = temp->next; temp->next = new Node(val); size++; } /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */ void addAtIndex(int index, int val) { if (index > size ) return; Node* temp = head; for(int i=0; i<index; i++) temp = temp->next; Node* temp1 = temp->next; temp->next = new Node(val); temp->next->next = temp1; size++; } /** Delete the index-th node in the linked list, if the index is valid. */ void deleteAtIndex(int index) { if (index >= size || index < 0) return; Node* temp = head; for(int i=0; i<index; i++) temp = temp->next; Node* temp1 = temp->next; temp->next = temp1->next; temp1->next = NULL; size--; delete temp1; } }; /** * 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); */

运行时间:52ms

运行内存:19.3M

  • LeetCode

    LeetCode(力扣)是一个全球极客挚爱的高质量技术成长平台,想要学习和提升专业能力从这里开始,充足技术干货等你来啃,轻松拿下 Dream Offer!

    209 引用 • 72 回帖 • 1 关注
  • LinkList
    9 引用 • 3 回帖
  • Easy
    101 引用 • 10 回帖

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...

推荐标签 标签

  • Anytype
    3 引用 • 31 回帖 • 14 关注
  • WiFiDog

    WiFiDog 是一套开源的无线热点认证管理工具,主要功能包括:位置相关的内容递送;用户认证和授权;集中式网络监控。

    1 引用 • 7 回帖 • 605 关注
  • jsDelivr

    jsDelivr 是一个开源的 CDN 服务,可为 npm 包、GitHub 仓库提供免费、快速并且可靠的全球 CDN 加速服务。

    5 引用 • 31 回帖 • 92 关注
  • App

    App(应用程序,Application 的缩写)一般指手机软件。

    91 引用 • 384 回帖
  • H2

    H2 是一个开源的嵌入式数据库引擎,采用 Java 语言编写,不受平台的限制,同时 H2 提供了一个十分方便的 web 控制台用于操作和管理数据库内容。H2 还提供兼容模式,可以兼容一些主流的数据库,因此采用 H2 作为开发期的数据库非常方便。

    11 引用 • 54 回帖 • 664 关注
  • SVN

    SVN 是 Subversion 的简称,是一个开放源代码的版本控制系统,相较于 RCS、CVS,它采用了分支管理系统,它的设计目标就是取代 CVS。

    29 引用 • 98 回帖 • 685 关注
  • Sandbox

    如果帖子标签含有 Sandbox ,则该帖子会被视为“测试帖”,主要用于测试社区功能,排查 bug 等,该标签下内容不定期进行清理。

    425 引用 • 1250 回帖 • 598 关注
  • Logseq

    Logseq 是一个隐私优先、开源的知识库工具。

    Logseq is a joyful, open-source outliner that works on top of local plain-text Markdown and Org-mode files. Use it to write, organize and share your thoughts, keep your to-do list, and build your own digital garden.

    7 引用 • 69 回帖 • 4 关注
  • Redis

    Redis 是一个开源的使用 ANSI C 语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value 数据库,并提供多种语言的 API。从 2010 年 3 月 15 日起,Redis 的开发工作由 VMware 主持。从 2013 年 5 月开始,Redis 的开发由 Pivotal 赞助。

    286 引用 • 248 回帖 • 21 关注
  • 思源笔记

    思源笔记是一款隐私优先的个人知识管理系统,支持完全离线使用,同时也支持端到端加密同步。

    融合块、大纲和双向链接,重构你的思维。

    24524 引用 • 100367 回帖
  • WordPress

    WordPress 是一个使用 PHP 语言开发的博客平台,用户可以在支持 PHP 和 MySQL 数据库的服务器上架设自己的博客。也可以把 WordPress 当作一个内容管理系统(CMS)来使用。WordPress 是一个免费的开源项目,在 GNU 通用公共许可证(GPLv2)下授权发布。

    66 引用 • 114 回帖 • 205 关注
  • PHP

    PHP(Hypertext Preprocessor)是一种开源脚本语言。语法吸收了 C 语言、 Java 和 Perl 的特点,主要适用于 Web 开发领域,据说是世界上最好的编程语言。

    179 引用 • 408 回帖 • 486 关注
  • Facebook

    Facebook 是一个联系朋友的社交工具。大家可以通过它和朋友、同事、同学以及周围的人保持互动交流,分享无限上传的图片,发布链接和视频,更可以增进对朋友的了解。

    4 引用 • 15 回帖 • 438 关注
  • 数据库

    据说 99% 的性能瓶颈都在数据库。

    345 引用 • 724 回帖
  • Vditor

    Vditor 是一款浏览器端的 Markdown 编辑器,支持所见即所得、即时渲染(类似 Typora)和分屏预览模式。它使用 TypeScript 实现,支持原生 JavaScript、Vue、React 和 Angular。

    364 引用 • 1839 回帖
  • 又拍云

    又拍云是国内领先的 CDN 服务提供商,国家工信部认证通过的“可信云”,乌云众测平台认证的“安全云”,为移动时代的创业者提供新一代的 CDN 加速服务。

    20 引用 • 37 回帖 • 566 关注
  • 爬虫

    网络爬虫(Spider、Crawler),是一种按照一定的规则,自动地抓取万维网信息的程序。

    106 引用 • 275 回帖
  • GitHub

    GitHub 于 2008 年上线,目前,除了 Git 代码仓库托管及基本的 Web 管理界面以外,还提供了订阅、讨论组、文本渲染、在线文件编辑器、协作图谱(报表)、代码片段分享(Gist)等功能。正因为这些功能所提供的便利,又经过长期的积累,GitHub 的用户活跃度很高,在开源世界里享有深远的声望,并形成了社交化编程文化(Social Coding)。

    210 引用 • 2040 回帖
  • 人工智能

    人工智能(Artificial Intelligence)是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门技术科学。

    152 引用 • 279 回帖
  • Maven

    Maven 是基于项目对象模型(POM)、通过一小段描述信息来管理项目的构建、报告和文档的软件项目管理工具。

    186 引用 • 318 回帖 • 264 关注
  • Shell

    Shell 脚本与 Windows/Dos 下的批处理相似,也就是用各类命令预先放入到一个文件中,方便一次性执行的一个程序文件,主要是方便管理员进行设置或者管理用的。但是它比 Windows 下的批处理更强大,比用其他编程程序编辑的程序效率更高,因为它使用了 Linux/Unix 下的命令。

    124 引用 • 74 回帖
  • Typecho

    Typecho 是一款博客程序,它在 GPLv2 许可证下发行,基于 PHP 构建,可以运行在各种平台上,支持多种数据库(MySQL、PostgreSQL、SQLite)。

    12 引用 • 67 回帖 • 443 关注
  • HHKB

    HHKB 是富士通的 Happy Hacking 系列电容键盘。电容键盘即无接点静电电容式键盘(Capacitive Keyboard)。

    5 引用 • 74 回帖 • 493 关注
  • 电影

    这是一个不能说的秘密。

    122 引用 • 608 回帖
  • Kubernetes

    Kubernetes 是 Google 开源的一个容器编排引擎,它支持自动化部署、大规模可伸缩、应用容器化管理。

    116 引用 • 54 回帖
  • jsoup

    jsoup 是一款 Java 的 HTML 解析器,可直接解析某个 URL 地址、HTML 文本内容。它提供了一套非常省力的 API,可通过 DOM,CSS 以及类似于 jQuery 的操作方法来取出和操作数据。

    6 引用 • 1 回帖 • 493 关注
  • RYMCU

    RYMCU 致力于打造一个即严谨又活泼、专业又不失有趣,为数百万人服务的开源嵌入式知识学习交流平台。

    4 引用 • 6 回帖 • 52 关注