[LeetCode] 19. Remove Nth Node From End of List 移除链表倒数第N个节点
2024-10-19 18:01:37
Given a linked list, remove the nth node from the end of list and return its head.
For example,
Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Try to do this in one pass.
这道题让我们移除链表倒数第N个节点,限定n一定是有效的,即n不会大于链表中的元素总数。还有题目要求一次遍历解决问题,那么就得想些比较巧妙的方法了。比如首先要考虑的时,如何找到倒数第N个节点,由于只允许一次遍历,所以不能用一次完整的遍历来统计链表中元素的个数,而是遍历到对应位置就应该移除了。那么就需要用两个指针来帮助解题,pre 和 cur 指针。首先 cur 指针先向前走N步,如果此时 cur 指向空,说明N为链表的长度,则需要移除的为首元素,那么此时返回 head->next 即可,如果 cur 存在,再继续往下走,此时 pre 指针也跟着走,直到 cur 为最后一个元素时停止,此时 pre 指向要移除元素的前一个元素,再修改指针跳过需要移除的元素即可,参见代码如下:
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
if (!head->next) return NULL;
ListNode *pre = head, *cur = head;
for (int i = ; i < n; ++i) cur = cur->next;
if (!cur) return head->next;
while (cur->next) {
cur = cur->next;
pre = pre->next;
}
pre->next = pre->next->next;
return head;
}
};
Github 同步地址:
https://github.com/grandyang/leetcode/issues/19
类似题目:
参考资料:
https://leetcode.com/problems/remove-nth-node-from-end-of-list/
LeetCode All in One 题目讲解汇总(持续更新中...)
最新文章
- 关于CommonJS规范摘录
- 【Spring-web】RestTemplate源码学习
- JArray数组每个JObject对象添加一个键值对
- iOS开发——源代码管理——git(分布式版本控制和集中式版本控制对比,git和SVN对比,git常用指令,搭建GitHub远程仓库,搭建oschina远程仓库 )
- MONO 说谈
- include动作标记和include指令标记学习笔记
- 在EF的code frist下写稳健的权限管理系统:MVC过滤拦截,权限核心(五)
- PHP类中的__get()和__set函数到底有什么用?
- 零基础学习云计算及大数据DBA集群架构师【预科2015年12月14日周一】
- 使用 CodeIgniter 框架快速开发 PHP 应用(四)
- 嵌套for in循环组合cat方式文件中包含空格问题
- python的切片操作
- PHPstorm 2017激活
- python之路--内置函数03
- Redis + keepalived 高可用行配置检测脚本
- nginx使用https协议
- python----常用模块(random,string,time&;datetime,os,sys,xpinyin(拼音))
- SpringBoot 调用 mysql存储过程的实战
- 2017上海C++面试
- recv用TCP和TUDP下的区别