【LeetCode707】设计链表

简介: 哨兵节点在树和链表中被广泛用作伪头、伪尾等,通常不保留任何数据。通常使用伪头来简化插入和删除。所以下面也用了伪头结点,所以注意题目中找第index个结点,还是从0号节点开始计算的,这里注意题目说的“假设链表中所有节点都是0-index的”,这里的0并非包括伪头节点。。就是说伪头节点的index并非是0,尤其注意这种边界问题。如下图的栗子:

一、题目

image.png


二、思路

常规题,注意边界。


哨兵节点在树和链表中被广泛用作伪头、伪尾等,通常不保留任何数据。通常使用伪头来简化插入和删除。所以下面也用了伪头结点,所以注意题目中找第index个结点,还是从0号节点开始计算的,这里注意题目说的“假设链表中所有节点都是0-index的”,这里的0并非包括伪头节点。。就是说伪头节点的index并非是0,尤其注意这种边界问题。

如下图的栗子:

image.png

题目的增加和删除节点、获得index位置的节点,都是常规操作,另外可以先写addAtIndex函数,因为这样addAtHead和addAtTail都能直接使用这个addAtIndex函数了,做到代码复用。


三、代码

3.1 Python版本

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None 
class MyLinkedList:
    def __init__(self):
        self.size = 0
        self.head = ListNode(0)
    def get(self, index: int) -> int:
        if index >= self.size or index < 0:
            return -1
        target = self.head 
        for i in range(index + 1):
            target = target.next
        return target.val
    def addAtHead(self, val: int) -> None:
        self.addAtIndex(0, val)
    def addAtTail(self, val: int) -> None:
        self.addAtIndex(self.size, val)
    def addAtIndex(self, index: int, val: int) -> None:
        if index > self.size:
            return 
        if index < 0:
            index = 0
        # 可以add了,计数加1 
        self.size += 1
        # 找到目标index节点的前一个节点
        pre = self.head 
        for i in range(index):# 到第index-1
            pre = pre.next    
        node = ListNode(val)
        # 插入值为val的节点
        node.next = pre.next 
        pre.next = node
    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size:
            return 
        self.size -= 1
        # 找到目标index节点的前一个节点
        pre = self.head 
        for i in range(index):# 到第index-1
            pre = pre.next    
        pre.next = pre.next.next
# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)


相关文章
|
机器学习/深度学习 算法 数据挖掘
|
7月前
RT-DETR改进策略【模型轻量化】| 替换骨干网络为 GhostNet V3 2024华为的重参数轻量化模型
RT-DETR改进策略【模型轻量化】| 替换骨干网络为 GhostNet V3 2024华为的重参数轻量化模型
221 2
RT-DETR改进策略【模型轻量化】| 替换骨干网络为 GhostNet V3 2024华为的重参数轻量化模型
|
10月前
|
人工智能 TensorFlow 算法框架/工具
《C++与人工智能库的完美邂逅:环境配置全攻略》
本文介绍了如何在C++环境中配置流行的人工智能库,如TensorFlow、PyTorch和OpenCV,涵盖库的选择、环境准备、具体配置步骤及常见问题解决方法,助力开发者高效构建智能化应用。
166 4
|
12月前
|
缓存 测试技术 API
电商平台 API 接入技术要点深度剖析
本文介绍了高效使用电商平台API的关键步骤。首先,深入理解API文档,明确功能权限与参数格式要求;其次,选择合适的接入方式,如HTTP/HTTPS协议和RESTful API;接着,实施身份验证与授权机制,确保数据安全传输;此外,还需关注性能优化、安全防护、监控与日志记录,以提升系统稳定性和响应速度;最后,进行充分测试与调试,并关注API版本更新,确保长期兼容性。
|
Java Linux Maven
Autogen4j: the Java version of Microsoft AutoGen
Java version of Microsoft AutoGen, Enable Next-Gen Large Language Model Applications
|
JavaScript Java 测试技术
基于springboot+vue.js的电商平台附带文章和源代码设计说明文档ppt
基于springboot+vue.js的电商平台附带文章和源代码设计说明文档ppt
131 1
基于springboot+vue.js的电商平台附带文章和源代码设计说明文档ppt
|
Linux 数据处理
探索Linux中的namei命令:文件路径解析的利器
`namei`是Linux工具,解析文件路径展示每个组件详情,包括类型、权限、属主等。它递归从根目录开始,帮助理解文件系统结构,尤其处理符号链接和挂载点。使用 `-l` 选项提供长格式输出, `-m` 以挂载点显示, `-x` 显示调试信息。示例用法如解析`/home/user/documents/report.txt`路径。注意权限、路径正确性及符号链接影响。可与其他命令结合使用。
|
前端开发 JavaScript C++
深入探索WebAssembly在前端性能优化中的应用
随着Web应用的功能越来越复杂,传统的JavaScript解释执行模式已经逐渐成为性能瓶颈。本文将介绍WebAssembly(以下简称Wasm)的基本概念、优势以及如何在现代Web开发中利用Wasm提升前端性能。我们将通过实际案例分析Wasm在处理高性能计算任务时相比JavaScript的优势,并探讨如何将Wasm集成到现有的前端项目中,以实现无缝的性能优化。本文旨在为前端开发者提供一个全面的Wasm应用指南,帮助他们充分利用这一新技术,提升Web应用的响应速度和用户体验。
355 0
|
开发工具 git
git add也能出错?
git add也能出错?
|
SQL 数据库连接 容器
Foxpro数据库连接错误解决方法--【VFP DBF文件不是一个有效的路径。 确定路径名称拼写是否正确,以及是否连接到文件存放的服务器】
直接访问vfp dbf文件时报错: 错误描述: 'd:\vfpData\test.dbf'不是一个有效的路径。 确定路径名称拼写是否正确,以及是否连接到文件存放的服务器。 解决办法:Data Source=目录!!!!!!(d:\vfpData) (1)--------------------...
1833 0