首页 > 试题广场 >

删除链表的倒数第n个节点

[编程题]删除链表的倒数第n个节点
  • 热度指数：236105 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个链表，删除链表的倒数第 n 个节点并返回链表的头指针
例如，
给出的链表为: , .
删除了链表的倒数第 个节点之后,链表变为.

数据范围： 链表长度 ，链表中任意节点的值满足 
要求：空间复杂度 ，时间复杂度
备注：
题目保证 一定是有效的
示例1

输入

{1,2},2

输出

{2}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
开通博客
头像 Maokt
发表于 2021-07-13 10:57:33
精华题解 算法思想一：双指针 解题思路 由于我们需要找到倒数第 n 个节点，因此可以使用两个指针fast 和 slow 同时对链表进行遍历，并且 fast 比 slow 超前 n 个节点。当 fast 遍历到链表的末尾时，slow 就恰好处于倒数第 n 个节点。 具体地，初始时 fast 和 sl 展开全文
去ta的博客 赞 (28) 回复(2) 收起
头像 牛客题解官
发表于 2022-04-22 11:29:45
精华题解 题目的主要信息： 给定一个链表，要删除链表倒数第n个节点，并返回链表的头 题目保证链表长度一定大于等于nnn 举一反三： 学习完本题的思路你可以解决如下题目： BM4.合并有序链表 BM5.合并k个已排序的链表 BM6.判断链表中是否有环 BM7.链表中环的入口节点 BM8.链表中倒数最后k个节 展开全文
去ta的博客 赞 (13) 回复(6) 收起
头像 未来0116
发表于 2021-07-15 09:52:19
精华题解 一.题目描述NC53删除链表的倒数第n个节点题目链接:https://www.nowcoder.com/practice/f95dcdafbde44b22a6d741baf71653f6?tpId=188&&tqId=38587&rp=1&ru=/activity/o 展开全文
去ta的博客 赞 (8) 回复(0) 收起
头像 SandMonth
发表于 2021-07-11 18:08:19
精华题解 删除链表的倒数第n个节点给定一个链表，删除链表的倒数第 nn 个节点并返回链表的头指针 示例输入：{1,2},2返回值：{2} 方法一 存入集合模拟 将所有元素存入vector中获取倒数第n的位置将其转换，但倒数第一个和正数第一个需要特判一下 代码 ListNode* removeNth 展开全文
去ta的博客 赞 (5) 回复(1) 收起
头像 鸠摩罗什
发表于 2021-07-18 22:24:07
精华题解 描述        给定一个链表，删除链表的倒数第n个节点并返回链表的头指针。例如，给出的链表为: 1→2→3→4→5, n= 2。删除了链表的倒数第n个节点之后,链表变为1→2→3→5.备注： 题目保证n一定是有效的请 展开全文
去ta的博客 赞 (0) 回复(2) 收起
头像 一只弱小的Kid
发表于 2020-09-04 16:14:20
解法 可以通过快指针先走K步 慢指针先指向head，导致 快指针和慢指针相差K个结点，然后快指针移到末尾 这个时候慢指针就是倒数第K个结点了。然后在遍历的时候 记录下慢指针的前一个结点，用来删除就OK了。 思路 import java.util.*; /* * public class List 展开全文
去ta的博客 赞 (29) 回复(4) 收起
头像 LifelongCode
发表于 2021-01-19 16:19:44
解法：快慢指针快指针先走n步，然后再和慢指针一起走，此时当快指针走完的时候，慢指针则刚好走到倒数的第n+1个结点，跳过倒数的第n个结点 public class Solution { /** * * @param head ListNode类 * @para 展开全文
去ta的博客 赞 (13) 回复(0) 收起
头像 天生撅墙
发表于 2020-09-02 11:04:54
删除链表的倒数第n个节点首先，我们要清楚链表的长度length，这样的话，要删除倒数第n个节点的话，就是删除正数的第（length - n）个节点（从 0 开始遍历链表）（当删除倒数第length的节点时例外，因为我们遍历链表的时候从 0 开始，所以这个时候我们需要单独将条件提出）。其次，当我们遍历 展开全文
去ta的博客 赞 (12) 回复(1) 收起
头像 数据结构和算法
发表于 2021-04-02 17:02:30
1，非递归解决 这题让删除链表的倒数第n个节点，首先最容易想到的就是先求出链表的长度length，然后就可以找到要删除链表的前一个结点，让他的前一个结点指向要删除结点的下一个结点即可，这里就以示例为例画个图看一下再来看下代码 public ListNode removeNthFromEnd( 展开全文
去ta的博客 赞 (10) 回复(1) 收起
头像 王清楚
发表于 2021-03-24 12:08:32
这道题目其实和输出链表的倒数第n个结点是基本上一致的。https://blog.nowcoder.net/n/4e57664df6974486bc352aa5a1e4613c和上一道题一样，定义快慢指针，快指针先走n步，然后快慢指针一起走，快指针走到空的时候慢指针正好在倒数第n个结点上。区别的地方只 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 牛客82035003号
发表于 2022-04-28 21:56:33
struct ListNode* removeNthFromEnd(struct ListNode* head, int n ) {     if(head ==&nbs 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 NiimiSora
发表于 2022-04-29 11:01:32
思路 同#链表中倒数最后k个结点#,使用快慢指针。 快指针比慢指针先n步，快慢指针同步前进，快指针碰到null时，慢指针就是待删除结点，比起上一题，需要再维护一个pre结点，记录slow指针前面的结点，最后逻辑删除slow结点，返回head。 实现 import java.util.*; publ 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 生来逆旅单行道
发表于 2021-04-26 15:10:16
题目描述给定一个链表，删除链表的倒数第 nn 个节点并返回链表的头指针例如，给出的链表为: 1→2→3→4→5 n=2.删除了链表的倒数第 n个节点之后,链表变为1→2→3→5. 备注：题目保证 n一定是有效的请给出请给出时间复杂度为O(n) 的算法 思路（通俗易懂版）：这题首先大家想的思路就是求出 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 yShane
发表于 2021-11-05 10:33:28
利用双指针法的python实现： # class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 我要来
发表于 2021-08-11 22:07:00
思路：1.求链表的长度length2.如果要删除的时头结点，即length==n，直接返回头结点的下一个结点。3.若非头结点，则找到待删除结点的父结点，即第length-n-1个。4.将父结点的子节点指向子结点的子结点。5.返回head public ListNode removeNthFromEn 展开全文
去ta的博客 赞 (2) 回复(0) 收起

问题信息

链表 双指针
难度：
383条回答 19984浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号