LeetCode(19):删除链表的倒数第N个节点
2023-09-14 09:01:23 时间
Medium!
题目描述:
给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
示例:
给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后,链表变为 1->2->3->5.
说明:
给定的 n 保证是有效的。
进阶:
你能尝试使用一趟扫描实现吗?
解题思路:
这道题让我们移除链表倒数第N个节点,限定n一定是有效的,即n不会大于链表中的元素总数。还有题目要求我们一次遍历解决问题,那么就得想些比较巧妙的方法了。比如我们首先要考虑的是,如何找到倒数第N个节点,由于只允许一次遍历,所以不能用一次完整的遍历来统计链表中元素的个数,而是遍历到对应位置就应该移除了。那么我们需要用两个指针来帮助我们解题,pre和cur指针。首先cur指针先向前走N步,如果此时cur指向空,说明N为链表的长度,则需要移除的为首元素,此时返回head->next即可,如果cur存在,再继续往下走,此时pre指针也跟着走,直到cur为最后一个元素时停止,此时pre指向要移除元素的前一个元素,再修改指针跳过需要移除的元素即可。
C++代码:
1 class Solution { 2 public: 3 ListNode* removeNthFromEnd(ListNode* head, int n) { 4 if (!head->next) return NULL; 5 ListNode *pre = head, *cur = head; 6 for (int i = 0; i < n; ++i) cur = cur->next; 7 if (!cur) return head->next; 8 while (cur->next) { 9 cur = cur->next; 10 pre = pre->next; 11 } 12 pre->next = pre->next->next; 13 return head; 14 } 15 };
相关文章
- LeetCode每日一题-1:反转链表
- LeetCode每日一题-5:删除排序链表中的重复元素
- leetcode 191 二进制中1的个数 js 实现
- ☆打卡算法☆LeetCode 206. 反转链表 算法解析
- ☆打卡算法☆LeetCode 207. 课程表 算法解析
- ☆打卡算法☆LeetCode 221. 最大正方形 算法解析
- ☆打卡算法☆LeetCode 203. 移除链表元素 算法解析
- LeetCode笔记:Biweekly Contest 84
- <leetcode刷题-数组> 【动态规划】【贪心算法】买卖股票的最佳时机
- 《三战Leetcode》寻找有序数组的中位数
- LeetCode周赛305,两千人通过第四题,手速场太可怕……
- leetcode-54螺旋矩阵
- leetcode 792_单词编码
- 图解剑指 Offer II 024. 反转链表(LeetCode)
- leetcode 141. 环形链表 js 实现
- LeetCode 141. 环形链表
- LeetCode 905. 按奇偶排序数组
- Leetcode No.147 对链表进行插入排序
- 【数据结构与算法】:交换排序之快速排序(手绘图解+LeetCode原题)
- JavaScript刷LeetCode-字符串类解题技巧_2023-02-27
- 用Js怒刷LeetCode_2023-02-27
- LeetCode | 删除链表的倒数第 N 个结点
- LeetCode 82:删除排序链表中的重复元素 II
- LeetCode-347-前K个高频元素
- 【拿捏链表(Ⅱ)】—Leetcode删除排序链表中的重复元素
- [数据结构]链表OJ(leetcode)
- leetcode每日一练:将句子排序
- leetcode:数组中的第K个最大元素
- LeetCode——根据二叉树创建字符串与二叉树的最近公共祖先