链接：删除链表的倒数第N个节点
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
题解一
一个直观的想法是一次遍历计算链表长度，之后对于给定的n,可以很快找到欲删除的结点。
题解二
对于一个问题，最好是能掌握多种解法，这样才能将一道题的价值最大化。
本解法是力扣Leetcode官方提供的解法，即利用栈先进后出的特点，即可一次遍历求出欲删除的结点,代码如下：
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(0, head);
stack<ListNode*> stk;
ListNode* cur = dummy;
while (cur) {
stk.push(cur);
cur = cur->next;
}
for (int i = 0; i < n; ++i) {
stk.pop();
}
ListNode* prev = stk.top();
prev->next = prev->next->next;
ListNode* ans = dummy->next;
delete dummy;
return ans;
}
};
题解三
利用快慢指针，可以优雅的解决这个问题。
由于我们需要找到倒数第 n个节点，因此我们可以使用两个指针 first和 second 同时对链表进行遍历，并且 first 比 second超前 n 个节点。当 first遍历到链表的末尾时，second 就恰好处于倒数第 n 个节点。
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(0, head);
ListNode* first = 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;
ListNode* ans = dummy->next;
delete dummy;
return ans;
}
};