首页 > 其他分享 >Leetcode707. 设计链表

Leetcode707. 设计链表

时间:2023-03-09 19:23:22浏览次数:39  
标签:index Leetcode707 val int 链表 设计 ListNode 节点

题目描述:

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性:val 和 next。val 是当前节点的值,next 是指向下一个节点的指针/引用。如果要使用双向链表,则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

 

在链表类中实现这些功能:

  • get(index):获取链表中第 index 个节点的值。如果索引无效,则返回-1。
  • addAtHead(val):在链表的第一个元素之前添加一个值为 val 的节点。插入后,新节点将成为链表的第一个节点。
  • addAtTail(val):将值为 val 的节点追加到链表的最后一个元素。
  • addAtIndex(index,val):在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度,则该节点将附加到链表的末尾。如果 index 大于链表长度,则不会插入节点。如果index小于0,则在头部插入节点。
  • deleteAtIndex(index):如果索引 index 有效,则删除链表中的第 index 个节点。

 

示例:

MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2);   //链表变为1-> 2-> 3
linkedList.get(1);            //返回2
linkedList.deleteAtIndex(1);  //现在链表是1-> 3
linkedList.get(1);            //返回3

  

删除链表节点:

 

添加链表节点:

 

思路:

这道题目设计链表的五个接口:

  • 获取链表第index个节点的数值
  • 在链表的最前面插入一个节点
  • 在链表的最后面插入一个节点
  • 在链表第index个节点前面插入一个节点
  • 删除链表的第index个节点

可以说这五个接口,已经覆盖了链表的常见操作,是练习链表操作非常好的一道题目

链表操作的两种方式:

  1. 直接使用原来的链表来进行操作。
  2. 设置一个虚拟头结点在进行操作。

下面采用的设置一个虚拟头结点。

class ListNode{
    int val;
    ListNode next;
    public ListNode(int val){
        this.val = val;
    }
}
class MyLinkedList {
    int size;
    ListNode head;
    public MyLinkedList() {
        size=0;
        head = new ListNode(0);
    }
    
    public int get(int index) {
        if(index<0||index>=size){
            return -1;
        }
        ListNode currentNode = head;
        for(int i=0;i<=index;i++){
            currentNode = currentNode.next;
        }
        return currentNode.val;
    }
    
    public void addAtHead(int val) {
        addAtIndex(0,val);
    }
    
    public void addAtTail(int val) {
        addAtIndex(size,val);
    }
    
    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 addAtNode = new ListNode(val);
        addAtNode.next = pred.next;
        pred.next = addAtNode;
    }
    
    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;
    }
}

  

标签:index,Leetcode707,val,int,链表,设计,ListNode,节点
From: https://www.cnblogs.com/zhz123567/p/17201120.html

相关文章

  • [设计模式]设计模式之装饰器模式/包装模式【8】【待完善】
    1概述当你在编写代码时,需要扩展一个类的功能,或者是当前类的接口不能满足需求时,你会选择怎么做?重新编写子类,通过继承加入功能?修改原有类的接口使其符合现有环境?但你......
  • 需求分析之道——需求分析要做什么(C系架构设计法,sishuok)
    需求分析之道——需求分析要做什么。需求分析是架构师开始做架构设计的第一步,对架构师来讲非常非常的重要。因为需求分析能够告诉我们,到底我们要做什么,架构设计就是为了去......
  • 系统设计面试与现实完全不同
    当您面试软件开发工作时,您可能会遇到一些系统设计问题。特别是如果您正在寻求高级职位。像许多软件开发一样,面试问题与现实完全不同。面试是什么样的面试官给你一个服......
  • 索引设计原则
    满足业务需求的情况下,尽量降低主键的长度。插入数据时,尽量选择顺序插入,选择使用AUTO_INCREMENT自增主键。尽量不要使用UUID做主键或者是其他自然主键,如身份证号。业务操作......
  • 架构设计思想-“开闭原则”
    架构设计思想,其中有一种设计原则叫“开闭原则”,其核心是:一个对象对扩展开放,对修改关闭。就是说,一旦写好了某个类,就不要去轻易改动他,而是要保证它一直能运行下去,而面对新的......
  • Spring设计模式——代理模式[手写实现JDK动态代理]
    代理模式代理模式(ProxyPattern):是指为其他对象提供一种代理,以控制对这个对象的访问。代理对象在客户端和目标对象之间起到中介作用,代理模式属于结构型设计模式。使用代......
  • 一Spring框架基础--2设计模式
    一Spring框架基础--2设计模式1.3spring用到的设计模式1.3.1责任链模式有多个对象,每个对象持有对下一个对象的引用,这样就会形成一条链,请求在这条链上传递,直到某一对象......
  • 浅析三款大规模分布式文件系统架构设计
    什么是文件系统当提到文件系统,大部分人都很陌生。但我们每个人几乎每天都会使用到文件系统,比如大家打开Windows、macOS或者Linux,不管是用资源管理器还是Finder,都是在......
  • leetcode203. 移除链表元素
    题目描述:给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val==val 的节点,并返回 新的头节点 。示例1:输入:head=[1,2,6,3,4,5,6],......
  • day88 - 数据库函数设计-插入100w条数据
    数据库插入100w条数据CREATETABLE`app_user`(`id`BIGINT(20)UNSIGNEDNOTNULLAUTO_INCREMENT,`name`VARCHAR(50)DEFAULT''COMMENT'用户昵称',`email`V......