题目
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
代码
法一、栈
/*** 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:stack<ListNode*> st;ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* p = head;while(p) {st.push(p);p = p->next;}int x = 0;while(!st.empty()) {x++;if (x == n) {ListNode* t = st.top();st.pop();if (!st.empty()) { // 还有，证明要删除的不是第一个结点ListNode* l = st.top();l->next = t->next;delete t;return head;} else {return head->next;}}st.pop();}return nullptr;}
};
法二、递归
/*** 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 {
private:int x = 0; // 记录倒数第几个结点int n;void solve(ListNode* l, ListNode* p) {if (!p) {return ;}solve(p, p->next);x++;if (x == n) {l->next = p->next;delete p;}}
public:ListNode* removeNthFromEnd(ListNode* head, int n) {this->n = n;ListNode* fake = new ListNode();fake->next = head;ListNode* p = fake;solve(nullptr, p);return fake->next;}
};