当前位置：首页 > 编程日记 > 正文

刻意练习：LeetCode实战 -- Task11. 删除链表的倒数第N个节点

编程日记 2024-09-26 07:10:00

背景

本篇图文是LSGO软件技术团队组织的第二期基础算法（Leetcode）刻意练习训练营的打卡任务。本期训练营采用分类别练习的模式，即选择了五个知识点（数组、链表、字符串、树、贪心算法），每个知识点选择了三个简单、两个中等、一个困难等级的题目，共计三十道题，利用三十天的时间完成这组刻意练习。

本次任务的知识点：链表

链表（Linked List） 是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里除了存放本身数据（data fields）之外还存放其后继节点的指针（Pointer）。

使用链表结构可以克服数组需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

链表有很多种不同的类型：单向链表，双向链表以及循环链表。

给定一个链表，删除链表的倒数第n个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的n保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

第一种：先求链表长度的方法

思路：先求出链表的长度len，再求出要删除结点的位置index = len - n。这样就可以从头结点开始遍历到该位置，删除该结点即可。

执行结果：通过
执行用时：148 ms, 在所有 C# 提交中击败了 6.77% 的用户
内存消耗：24.6 MB, 在所有 C# 提交中击败了 5.43% 的用户

/*** Definition for singly-linked list.* public class ListNode {*     public int val;*     public ListNode next;*     public ListNode(int x) { val = x; }* }*/public class Solution
{public ListNode RemoveNthFormEnd(ListNode head, int n){int len = GetLength(head);int index = len - n;if (index == 0){head = head.next;return head;}ListNode temp = head;for (int i = 0; i < index - 1; i++){temp = temp.next;}temp.next = temp.next.next;return head;}public int GetLength(ListNode head){ListNode temp = head;int i = 0;while (temp != null){i++;temp = temp.next;}return i;}
}

第二种：双指针法

思路：使用两个指针，前面的指针p2先走n步，接着让后面的指针p1与p2同步走，p2走到终点，p1即走到要移除的结点位置。

执行结果：通过
执行用时：108 ms, 在所有 C# 提交中击败了 74.84% 的用户
内存消耗：24.8 MB, 在所有 C# 提交中击败了 5.43% 的用户

/*** Definition for singly-linked list.* public class ListNode {*     public int val;*     public ListNode next;*     public ListNode(int x) { val = x; }* }*/
public class Solution {public ListNode RemoveNthFromEnd(ListNode head, int n) {ListNode p1 = head;ListNode p2 = head;while (n > 0){p2 = p2.next;n--;}if (p2 == null) //移除头结点{return head.next;}while (p2.next != null){p2 = p2.next;p1 = p1.next;}p1.next = p1.next.next;return head;}
}

Python 语言

执行结果：通过
执行用时：48 ms, 在所有 Python3 提交中击败了 23.58% 的用户
内存消耗：13.5 MB, 在所有 Python3 提交中击败了 7.83% 的用户

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:p1 = headp2 = headwhile(n>0):p2 = p2.nextn-=1if(p2 is None): #移除头结点return head.nextwhile(p2.next):p1 = p1.nextp2 = p2.nextp1.next = p1.next.nextreturn head

来源

https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

往期活动

LSGO软件技术团队会定期开展提升编程技能的刻意练习活动，希望大家能够参与进来一起刻意练习，一起学习进步！

Python基础刻意练习活动即将开启，你参加吗？
Task01：变量、运算符与数据类型
Task02：条件与循环
Task03：列表与元组
Task04：字符串与序列
Task05：函数与Lambda表达式
Task06：字典与集合
Task07：文件与文件系统
Task08：异常处理
Task09：else 与 with 语句
Task10：类与对象
Task11：魔法方法
Task12：模块

我是终身学习者“老马”，一个长期践行“结伴式学习”理念的 中年大叔。

我崇尚分享，渴望成长，于2010年创立了“LSGO软件技术团队”，并加入了国内著名的开源组织“Datawhale”，也是“Dre@mtech”、“智能机器人研究中心”和“大数据与哲学社会科学实验室”的一员。

愿我们一起学习，一起进步，相互陪伴，共同成长。

后台回复「搜搜搜」，随机获取电子资源！
欢迎关注，请扫描二维码：

https://www.dkcj.cn/info/20383.html

刻意练习：LeetCode实战 -- Task11. 删除链表的倒数第N个节点

背景

相关文章：

https和http有什么区别?看下面介绍就知道了!

C#图片灰度处理(位深度24→位深度8),用灰度数组byte[]新建一个8位灰度图像Bitmap 。...

日期NSDate的使用

刻意练习：LeetCode实战 -- Task12. 合并K个排序链表

软测培训机构哪个比较好

刻意练习：LeetCode实战 -- Task13. 罗马数字转整数

[翻译]ASP.NET MVC 3 开发的20个秘诀（十二）[20 Recipes for Programming MVC 3]：缩放图片尺寸创建缩略图...

Vue.js双向绑定的实现原理

学习UI设计的一些小技巧你会了吗

30个精美的模板，贺卡，图形圣诞素材

刻意练习：LeetCode实战 -- Task14. 最长公共前缀

6.1.1 验证注解的使用

Javascript创建数组的方式你了解了吗

loadrunner另类玩法【测试帮日记公开课】

刻意练习：LeetCode实战 -- Task15. 有效的括号

对口令协议的几种攻击方式

初学者如何学Java开发

[算法] [常微分方程] [欧拉法改进欧拉法经典R-K算法]

刻意练习：LeetCode实战 -- Task16. 无重复字符的最长子串

轻松实现QQ用户接入

web前端培训之Javascript如何改变数组的长度?

刻意练习：LeetCode实战 -- Task17. 最长回文子串

CvBlobTrackerCC 多目标跟踪算法简析

linux基础学习（二）

ui设计培训需要什么基础?如何入门学习?

SQL Server日志清除的两种方法 .

刻意练习：LeetCode实战 -- Task18. 正则表达式匹配

CentOS7启动图形界面

Java培训学习步骤有哪些

extjs 4 tab panel得strip在IE下右偏解决办法