力扣707题解:设计链表(java)

2024-06-15 14:20

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

力扣707题解:设计链表

引言

LeetCode是一个广受欢迎的在线编程平台,它提供了大量的算法题目供程序员练习和挑战。第707题要求我们设计一个链表,这个链表支持以下操作:getaddAtHeadaddAtTailaddAtIndexdeleteAtIndex。本文将详细介绍如何使用Java实现这个链表。

题目描述

设计一个链表,支持以下所有操作,以供以后使用:

  • get(index):获取链表中第 index 个节点的值(索引从1开始)。
  • addAtHead(val):在链表的第一个元素之前添加一个值为 val 的新节点。
  • addAtTail(val):在链表的最后一个元素之后添加一个值为 val 的新节点。
  • addAtIndex(index, val):在链表中的第 index 个节点之前添加一个值为 val 的新节点。
  • deleteAtIndex(index):如果索引在1到n之间(含1和n),则删除链表中的第 index 个节点。

问题分析

为了实现这个链表,我们可以使用一个内部类ListNode来表示链表的节点,每个节点包含一个值和一个指向下一个节点的指针。链表类本身需要维护一个头节点指针,以及链表的长度。

算法设计

  1. 初始化:链表初始化时,使用一个哑节点作为头节点,实际的数据存储从哑节点的下一个节点开始。
  2. get(index):遍历链表,直到找到索引为index的节点。
  3. addAtHead(val):创建新节点,将其插入到头节点之后。
  4. addAtTail(val):遍历到尾节点,将新节点添加到尾节点之后。
  5. addAtIndex(index, val):如果索引为1,使用addAtHead;如果索引等于链表长度,使用addAtTail;否则,找到索引前一个节点,将新节点插入。
  6. deleteAtIndex(index):如果索引为1,删除头节点的下一个节点;否则,找到索引前一个节点,将其next指针指向要删除节点的下一个节点。

Java实现

    //size存储链表元素的个数int size;//虚拟头结点ListNode head;//初始化链表public MyLinkedList() {size = 0;head = new ListNode(0);}//获取第index个节点的数值,注意index是从0开始的,第0个节点就是头结点public int get(int index) {//如果index非法,返回-1if (index < 0 || index >= size) {return -1;}ListNode currentNode = head;//包含一个虚拟头节点,所以查找第 index+1 个节点for (int i = 0; i <= index; i++) {currentNode = currentNode.next;}return currentNode.val;}//在链表最前面插入一个节点,等价于在第0个元素前添加public void addAtHead(int val) {addAtIndex(0, val);}//在链表的最后插入一个节点,等价于在(末尾+1)个元素前添加public void addAtTail(int val) {addAtIndex(size, val);}// 在第 index 个节点之前插入一个新节点,例如index为0,那么新插入的节点为链表的新头节点。// 如果 index 等于链表的长度,则说明是新插入的节点为链表的尾结点// 如果 index 大于链表的长度,则返回空public void addAtIndex(int index, int val) {if (index > size) {return;}if (index < 0) {index = 0;}size++;//找到要插入节点的前驱ListNode pred = head;for (int i = 0; i < index; i++) {pred = pred.next;}ListNode toAdd = new ListNode(val);toAdd.next = pred.next;pred.next = toAdd;}//删除第index个节点public void deleteAtIndex(int index) {if (index < 0 || index >= size) {return;}size--;if (index == 0) {head = head.next;return;}ListNode pred = head;for (int i = 0; i < index ; i++) {pred = pred.next;}pred.next = pred.next.next;}
}

注意事项

  • 使用哑节点可以简化边界条件的处理。
  • addAtIndexdeleteAtIndex方法中,需要根据索引值选择不同的插入或删除策略。

结语

LeetCode第707题是一个链表操作的综合题目,通过这个问题,我们可以加深对链表操作的理解。掌握这个问题的解法,对于解决其他链表相关问题非常有帮助。


这篇关于力扣707题解:设计链表(java)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时,有没有考虑过 JVM 是如何把静态的字节码(byte code)转化为运行时对象的呢,这个问题看似简单,但清楚的同学相信也不会太多,这篇文章首先介绍 JVM 类初始化的机制,然后给出几个易出错的实例来分析,帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段,分别是:loading 、Linking、initialization

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权,允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true (Spring security默认会带有ROLE_前缀),去

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程,特意画了如下的类图,包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口,接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类,它们之间的依赖,构建起了整个框架。想要理解整个架构,最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文(security context)的信息。当前操作的用户是谁,该用户是否已经被认证,他拥有哪些角色权限…这些都被保

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物

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

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

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来,一站式有声阅读平台听书系统 🌟&nbsp;开篇:遇见未来,从“智听”开始 在这个快节奏的时代,你是否渴望在忙碌的间隙,找到一片属于自己的宁静角落?是否梦想着能随时随地,沉浸在知识的海洋,或是故事的奇幻世界里?今天,就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统,它正悄悄改变着我们的阅读方式,让未来触手可及! 📚&nbsp;第一站:海量资源,应有尽有 走进“智听