百度360必应搜狗淘宝本站头条
当前位置:网站首页 > 技术分类 > 正文

算法:删除链表的倒数第N个节点(Java版)

ztj100 2024-11-16 02:55 23 浏览 0 评论

删除链表的倒数第N个节点是一个经典的链表操作问题。为了解决这个问题,我们可以使用双指针的方法。

思路

首先让第一个指针先向前移动N+1步,然后两个指针同时向前移动,直到第一个指针到达链表的末尾。此时,第二个指针所指向的节点就是我们需要删除的倒数第N个节点。

初始化:

  • 创建一个虚拟头节点(dummy),并将其next指针指向链表的头节点(head)。
  • 初始化两个指针first和second,都指向虚拟头节点(dummy)。

移动first指针:

  • 使用循环将first指针向前移动n+1步。
  • 注意:此时first指针将位于要删除节点的前面的第n+1个位置。

同时移动first和second指针:

  • 使用循环同时移动first和second指针,直到first指针到达链表的末尾。
  • 在这个过程中,second指针将逐渐接近要删除的节点。

删除节点:

  • 当first指针到达链表末尾时,second指针将指向要删除的节点的前一个节点。
  • 修改second指针的next指针,使其跳过要删除的节点,直接指向下一个节点。

返回结果:

  • 返回虚拟头节点的next指针作为新的链表头节点。

下面是一个Java实现的示例:

Bash
public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode first = dummy;
        ListNode second = dummy;

        // 首先,让first指针向前移动n+1步
        for (int i = 0; i <= n; i++) {
            first = first.next;
        }

        // 然后,两个指针同时向前移动,直到first到达链表末尾
        while (first != null) {
            first = first.next;
            second = second.next;
        }

        // 删除second所指向的节点
        second.next = second.next.next;

        return dummy.next;
    }
}

在这个解法中,我们首先创建了一个虚拟头节点(dummy),它的作用是简化边界条件的处理。然后,我们使用两个指针first和second,首先让first指针向前移动n+1步,然后两个指针同时向前移动,直到first到达链表末尾。此时,second所指向的节点就是我们需要删除的倒数第N个节点。最后,我们修改second的next指针,跳过要删除的节点,从而完成删除操作。

时间复杂度:这个算法的时间复杂度是O(L),其中L是链表的长度。因为我们需要遍历整个链表一次。

空间复杂度:这个算法的空间复杂度是O(1)。我们只使用了常数级别的额外空间来存储指针。

总结

删除链表的倒数第N个节点的问题可以通过双指针的方法解决,时间复杂度为O(L),空间复杂度为O(1),是一种高效且节省空间的解法。

相关推荐

Sublime Text 4 稳定版 Build 4113 发布

IT之家7月18日消息知名编辑器SublimeText4近日发布了Build4113版本,是SublimeText4的第二个稳定版。IT之家了解到,SublimeTe...

【小白课程】openKylin便签贴的设计与实现

openKylin便签贴作为侧边栏的一个小插件,提供便捷的文本记录和灵活的页面展示。openKylin便签贴分为两个部分:便签列表...

“告别 Neovim!为什么我投奔了刚开源的 Zed 编辑器?”

...

壹啦罐罐 Android 手机里的 Xposed 都装了啥

这是少数派推出的系列专题,叫做「我的手机里都装了啥」。这个系列将邀请到不同的玩家,从他们各自的角度介绍手机中最爱的或是日常使用最频繁的App。文章将以「每周一篇」的频率更新,内容范围会包括iOS、...

电气自动化专业词汇中英文对照表(电气自动化专业英语单词)

专业词汇中英文对照表...

Python界面设计Tkinter模块的核心组件

我们使用一个模块,我们要熟悉这个模块的主要元件。如我们设计一个窗口,我们可以用Tk()来完成创建;一些交互元素,按钮、标签、编辑框用到控件;怎么去布局你的界面,我们可以用到pack()、grid()...

以色列发现“死海古卷”新残片(死海古卷是真的吗)

编译|陈家琦据艺术新闻网(artnews.com)报道,3月16日,以色列考古学家发现了死海古卷(DeadSeaScrolls)新残片。新出土的羊皮纸残片中包括以希腊文书写的《十二先知书》段落,这...

鸿蒙Next仓颉语言开发实战教程:订单列表

大家上午好,最近不断有友友反馈仓颉语言和ArkTs很像,所以要注意不要混淆。今天要分享的是仓颉语言开发商城应用的订单列表页。首先来分析一下这个页面,它分为三大部分,分别是导航栏、订单类型和订单列表部分...

哪些模块可以用在 Xposed for Lollipop 上?Xposed 模块兼容性解答

虽然已经有了XposedforLollipop的安装教程,但由于其还处在alpha阶段,一些Xposed模块能不能依赖其正常工作还未可知。为了解决大家对于模块兼容性的疑惑,笔者尽可能多...

利用 Fluid 自制 Mac 版 Overcast 应用

我喜爱收听播客,健身、上/下班途中,工作中,甚至是忙着做家务时。大多数情况下我会用MarcoArment开发的Overcast(Freemium)在iPhone上收听,这是我目前最喜爱的Po...

Avalonia日志组件实现与优化指南(ar日志表扣)

...

浅色Al云食堂APP代码(三)(手机云食堂)

以下是进一步优化完善后的浅色AI云食堂APP完整代码,新增了数据可视化、用户反馈、智能推荐等功能,并优化了代码结构和性能。项目结构...

实战PyQt5: 121-使用QImage实现一个看图应用

QImage简介QImage类提供了独立于硬件的图像表示形式,该图像表示形式可以直接访问像素数据,并且可以用作绘制设备。QImage是QPaintDevice子类,因此可以使用QPainter直接在图...

滚动条隐藏及美化(滚动条隐藏但是可以滚动)

1、滚动条隐藏背景/场景:在移动端,滑动的时候,会显示默认滚动条,如图1://隐藏代码:/*隐藏滚轮*/.ul-scrool-box::-webkit-scrollbar,.ul-scrool...

浅色AI云食堂APP完整代码(二)(ai 食堂)

以下是整合后的浅色AI云食堂APP完整代码,包含后端核心功能、前端界面以及优化增强功能。项目采用Django框架开发,支持库存管理、订单处理、财务管理等核心功能,并包含库存预警、数据导出、权限管理等增...

取消回复欢迎 发表评论: