目录题目题目链接思路复杂度代码题目题目链接19. 删除链表的倒数第 N 个结点 - 力扣LeetCodehttps://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/?envTypestudy-plan-v2envIdtop-100-liked思路统计链表长度通过一次遍历计算出链表的总节点数cnt。计算正数位置倒数第n个节点的前一个节点其正数位置为cnt - n从1开始计数。例如链表长度为5要删除倒数第2个节点则前一个节点是正数第3个节点。处理特殊情况如果cnt - n 0说明要删除的是头节点直接返回head-next。再次遍历找到前一个节点重新遍历链表找到第cnt - n个节点将它的next指针指向下下个节点从而跳过要删除的节点。返回头节点如果头节点被删除已提前返回新头否则返回原头节点。复杂度时间复杂度O(n)需要两次遍历链表每次遍历 O(n)总操作次数约为 2n仍属于线性时间复杂度。空间复杂度O(1)只使用了常数个额外指针变量不依赖链表长度。代码/** * 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) { // 第一次遍历统计链表长度 int cnt 0; // 记录节点总数 ListNode* cur head; // 临时指针用于遍历 while (cur ! nullptr) { cnt; cur cur-next; } // 计算要删除的节点的前一个节点的正数位置 // 倒数第 n 个节点的前一个节点是正数第 (cnt - n) 个节点从1开始计数 cnt cnt - n; // 如果要删除的是头节点即 cnt 0直接返回 head-next if (cnt 0) { return head-next; } // 第二次遍历找到第 cnt 个节点 cur head; // 重新指向头节点 int curcnt 0; // 记录当前遍历到的节点位置 while (cur ! nullptr) { curcnt; // 先递增此时 cur 指向第 curcnt 个节点 if (curcnt cnt) { // 当到达第 cnt 个节点时 // 删除它的下一个节点即倒数第 n 个节点 cur-next cur-next-next; break; // 删除后可以提前退出循环 } cur cur-next; // 继续向后移动 } // 返回原头节点注意如果删除的是头节点上面已返回新头 return head; } };