首页 > 其他分享 >《链表篇》---删除链表的倒数第N个节点(中等)

《链表篇》---删除链表的倒数第N个节点(中等)

时间:2024-10-31 18:20:50浏览次数:3  
标签:--- head ListNode cur next 链表 节点 倒数第

题目传送门 

方法一:计算链表长度(迭代)

1.计算链表长度,并且定义哑节点链接链表。

2.从哑节点开始前进length-n次。即为被删除节点的前置节点。

3.进行删除操作。

4.返回哑节点的后置节点

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //定义一个虚拟节点,并且链接链表
        ListNode dummy = new ListNode(0,head);
        ListNode cur = dummy;
        int length = getLength(head);//获取链表长度

        //从虚拟节点开始,前进length-n次,即为被删除节点的前置节点
        for(int i = 0; i < length-n; i++){
            cur = cur.next;
        }
        cur.next = cur.next.next;
        return dummy.next;

    }

    public int getLength(ListNode head){
        int length = 0;
        while(head != null){
            length++;
            head = head.next;
        }
        return length;
    }
}

方法二:栈

在 Java 中,虽然有 Stack 类,但推荐使用 Deque(例如 LinkedListArrayDeque)来实现栈的功能。主要原因有:

1. 设计上的问题

2. 性能优势

3. 双端队列的灵活性

4. 现代化的 API

 1.定义一个虚拟节点,用来找到结果链表的头结点。

2.将链表节点全部入栈,包括虚拟节点。

3.出n次栈。也就是刚好把要删除节点出栈。

4.记录栈顶元素的地址。也就是被删除节点的前置节点。

5.链接链表。将前置节点与后置节点链接起来。

6.返回虚拟节点的下一个节点。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        Deque<ListNode> stack = new LinkedList<ListNode>();
        ListNode cur = dummy;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        for (int i = 0; i < n; ++i) {
            stack.pop();
        }
        ListNode prev = stack.peek();
        prev.next = prev.next.next;
        ListNode ans = dummy.next;
        return ans;
    }
}

标签:---,head,ListNode,cur,next,链表,节点,倒数第
From: https://blog.csdn.net/m0_73456341/article/details/143377214

相关文章

  • 基础知识-7-选择结构【if switch】
    概念说明1.if与switch的作用与区别if语句用于根据一个条件表达式的结果来决定是否执行某个代码块。它可以处理各种类型的条件,包括范围判断和复杂的逻辑表达式。intnum=5;if(num>3){cout<<"num大于3"<<endl;}switch语句用于......
  • Ethernet 系列(6)-- 基础学习::OSI Model
    (写在前面:最近在学习车载以太网的知识,顺便记录一下知识点。)OSI(OpenSystemInterconnect)模型是一种网络通信框架,由国际标准化组织(‌ISO)在1985年提出,旨在为不同制造商和技术提供商的网络设备和软件提供一个通用的兼容和通信标准。这个模型将复杂的网络通信过程分解为七个独......
  • 《使用Gin框架构建分布式应用》阅读笔记:p272-p306
    《用Gin框架构建分布式应用》学习第15天,p272-p306总结,总35页。一、技术总结1.TDD(test-drivendevelopment)虽然经常看到TDD这个属于,从本人的工作经历看,实际开发中用得相对较少。2.unitest(单元测试)go语言开发中,使用testify进行单元测试开发。(1)创建测试文件测试文件以xx......
  • 108-二叉树-将有序数组转换为二叉搜索树
    树|二叉搜索树|数组|分治|二叉树二叉搜索树(BinarySearchTree,简称BST)和平衡二叉搜索树(BalancedBinarySearchTree)是计算机科学中非常重要的数据结构,广泛应用于各种算法和系统中。理解它们的定义、特点和性质对于掌握数据结构和算法至关重要。下面,我们将详细......
  • ChatGLM3-6B模型分析
    ChatGLM3是清华、智谱2023年开源的一款大模型。ChatGLM3-6B模型代码,目前还在研读中,尚未全部读完。图1为ChatGLM3-6B模型简图,其结构基于TransformerEncoder架构的Encoder,大体上与BERT架构类似。ChatGLM3实现模型架构时,已预置支持P-tuningv2微调结构,图7中的PrefixEncoder......
  • UcOs-III 源码阅读: os_mem.c
    //作用:固定大小内存管理器的代码,内存分区代码/***********************************************************************************************************uC/OS-III*TheReal......
  • 嵌入式课程day04-C语言运算符和选择结构
    2.3运算符2.3.1运算符介绍运算符:具有一定运算规则的符号。操作数:运算符的操作对象。~a   ---a就是~运算符的操作数。---单目运算符:运算符只有一个操作数3+5---35就是+运算符的操作数。---双目运算符:运算符有2个操作数    表达式1?表达式2:表达......
  • printf(“%d %d %d %d\n“,--i,i--,++i,i++);
    #include<stdio.h>intmain(){ inti=0;printf("%d%d%d%d\n",--i,i--,++i,i++);}第一次接触到这个问题,相信大家跟我一样,信心满满,心里想着“这不就是考,先++就先+再调用,后++就先调用再+”,于是把这一题秒了。--i,先减再调用,答案-1,i变为-1i--,先调用再减,答案-1,i变......
  • Filter -2024/10/31
    Filter表示过滤器,是JavaWeb三大组件(Servlet、Filter、Listener)之一packagecom.stdu.web.filter;importjavax.servlet.*;importjavax.servlet.annotation.WebFilter;importjava.io.IOException;@WebFilter("/*")publicclassFilter_demoimplementsFilter{......
  • 《程序员修炼之道:从小工到专家》阅读笔记1---程序员的责任与担当
    《程序员修炼之道:从小工到专家》,开篇关于责任的阐述如同一盏明灯,照亮了我对程序员这一职业的认知之路。责任,是程序员工作的基石。在软件开发的世界里,我们所编写的每一行代码都承载着重要的使命。这不仅仅是为了完成任务,更是为了确保软件的质量、稳定性和安全性。我们不能仅仅满足......