【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)


相关文章
|
机器学习/深度学习 算法 数据挖掘
|
8月前
RT-DETR改进策略【模型轻量化】| 替换骨干网络为 GhostNet V3 2024华为的重参数轻量化模型
RT-DETR改进策略【模型轻量化】| 替换骨干网络为 GhostNet V3 2024华为的重参数轻量化模型
246 2
RT-DETR改进策略【模型轻量化】| 替换骨干网络为 GhostNet V3 2024华为的重参数轻量化模型
|
11月前
|
人工智能 TensorFlow 算法框架/工具
《C++与人工智能库的完美邂逅:环境配置全攻略》
本文介绍了如何在C++环境中配置流行的人工智能库,如TensorFlow、PyTorch和OpenCV,涵盖库的选择、环境准备、具体配置步骤及常见问题解决方法,助力开发者高效构建智能化应用。
172 4
|
缓存 测试技术 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
|
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应用的响应速度和用户体验。
376 0
|
算法 Unix Linux
【Linux 库管理工具】深入解析pkg-config与CMake的集成与应用
【Linux 库管理工具】深入解析pkg-config与CMake的集成与应用
1079 0
|
SQL Oracle 关系型数据库
解读数据传输DTS技术架构及最佳实践
在阿里云数据库技术峰会上,阿里巴巴高级技术专家付大超(千震)针对于云计算时代最好的数据传输产品阿里云DTS的架构设计、基本原理以及相关的应用场景进行了精彩分享。帮助大家了解了阿里是如何实现异地多活和异构多活的,以及通过DTS轻松实现迁移、双同同步、容灾、订阅的真实案例。
14677 1
|
开发工具 git
git add也能出错?
git add也能出错?