Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(-1);
dummy->next = head;
ListNode* p = dummy;
ListNode* q = dummy;
for (int i = 0; i < n + 1; ++i) {
p = p->next;
} // p 移动 n + 1 次指向第 n + 1 个节点
// 此时 p 与 q 距离为 n + 1
while (p) {
p = p->next; // p 到达最后的空节点时
q = q->next; // q 到达倒数第 n + 1 个节点
}
// 要删除倒数第 n 个节点
// 让倒数第 n + 1 个节点的下一节点指向倒数第 n - 1 个节点即可
q->next = q->next->next;
return dummy->next;
}
};