题目
19. 删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1
输出：[]
示例 3：
输入：head = [1,2], n = 1
输出：[1]
提示：
- 链表中结点的数目为 sz
- 1 <= sz <= 30
- 0 <= Node.val <= 100
- 1 <= n <= sz
进阶：你能尝试使用一趟扫描实现吗？
我的代码（Python）
/**
* 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) {
if (head == nullptr || head->next == nullptr) {
return nullptr;
}
ListNode* t1 = head;
ListNode* t2 = head;
int cnt = 0;
while (t2->next != nullptr) {
t2 = t2->next;
cnt++;
if (cnt > n) {
t1 = t1->next;
}
}
if (cnt < n) {
return head->next;
}
t1->next = t1->next->next;
// ListNode* del = t1->next;
// t1->next = del->next;
// delete del;
return head;
}
};点评
这次换C++。时间上击败了100%，于是决定不再运行了，因为下次运行不一定多少😄
思路很简单，提到链表，基本上都要考虑多个指针/索引一起处理，迭代速度也有快慢。
虽然进阶解法指定只能遍历一次，不过严格说来，用一个指针遍历两次，和用一个指针遍历一次，应该消耗是一样的。
另外官方题解提到另一个常用技巧：头部添加一个哑结点。我的做法确实是在头部时有些情况单独处理（cnt < n判断分支），如果这样应该会容易一些。
baddif@gmail.com
AI简历优化站
AI求职跟踪器（建设中）
主站（建设中）
相关平台
Github Issues / Notion / Blog