亳州网站建设,wordpress京东主题,天元建设集团有限公司宋卫志,焦作做网站的公司文章目录 写在前面Tag题目来源解题思路方法一#xff1a;统计节点个数方法二#xff1a;双指针 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法#xff0c;两到三天更新一篇文章#xff0c;欢迎催更…… 专栏内容以分析题目为主#xff0c;并附带一些对于本… 文章目录 写在前面Tag题目来源解题思路方法一统计节点个数方法二双指针 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法两到三天更新一篇文章欢迎催更…… 专栏内容以分析题目为主并附带一些对于本题涉及到的数据结构等内容进行回顾与总结文章结构大致如下部分内容会有增删 Tag介绍本题牵涉到的知识点、数据结构题目来源贴上题目的链接方便大家查找题目并完成练习题目解读复述题目确保自己真的理解题目意思并强调一些题目重点信息解题思路介绍一些解题思路每种解题思路包括思路讲解、实现代码以及复杂度分析知识回忆针对今天介绍的题目中的重点内容、数据结构进行回顾总结。 Tag
【链表-删除节点】【迭代】 题目来源
19. 删除链表的倒数第 N 个结点 解题思路
方法一统计节点个数
思路
一种朴素的方法是首先统计链表中节点的个数 m倒数第 n 个节点就是正数第 m - n 1 个节点。我们从头结点开始找到正数第 m - n 个节点要删除节点的前一个节点直接将该节点的指针指向下下个节点即可。
代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:const int getLength(ListNode* head) {int len 0;while (head) {len;head head-next;}return len;}ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummy new ListNode(0, head);int m getLength(head);ListNode* cur dummy;for (int i 0; i m - n; i) {cur cur-next;}cur-next cur-next-next;return dummy-next;}
};复杂度分析
时间复杂度 O ( m ) O(m) O(m) m m m 为链表的长度。
空间复杂度 O ( 1 ) O(1) O(1)。
方法二双指针
思路
我们先用一个指针指向链表的第 n 个节点此时增加另一个指针指向头结点接着让两个指针同时向链表尾部移动每一移动一个位置当第一个指针到达 nullptr 时我们也就找到了需要删除的节点。
如果我们利用 代码 中的 while 循环就找到了要删除节点的上一个节点此时直接将该节点的指针指向下下个节点即可。
代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode *first head;ListNode *dummy new ListNode(0, head);ListNode *second dummy;for(int i 0; i n; i)first first-next;while(first){first first-next;second second-next;}second-next second-next-next;return dummy-next;}
};复杂度分析
时间复杂度 O ( m ) O(m) O(m) m m m 为链表的长度。
空间复杂度 O ( 1 ) O(1) O(1)。 写在最后
如果您发现文章有任何错误或者对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度的方法欢迎评论区交流。
最后感谢您的阅读如果有所收获的话可以给我点一个 哦。
