【算法面试必刷】19. 删除链表的倒数第 N 个结点
目录
题目
题目链接
思路
复杂度
代码
题目
题目链接
19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/?envType=study-plan-v2&envId=top-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; } };