19. 删除链表的倒数第 N 个结点

题目链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

这道题目，内存占用会比较多，空间复杂度比较高，不过还好vector里保存的都是指针，没看官方题解，省得记不住，还是自己的思路比较容易记忆。

/**
 * 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) {
        vector<ListNode*> ln;  // store all nodes to vector
        ListNode* p = head;
        while (p) {
            ln.push_back(p);
            p = p->next;
        }
        if (n == 1 && ln.size() > 1) {  // remove the last node
            ln[ln.size() - 2]->next = nullptr;
            return head;
        } else if (n == ln.size()) {  // remove the first node
            return head->next;
        }
        ln[ln.size() - n - 1]->next = ln[ln.size() - n + 1];  // remove the middle node
        return head;
    }
};

/**

* 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) {

vector<ListNode*> ln; // store all nodes to vector

ListNode* p = head;

while (p) {

ln.push_back(p);

p = p->next;

}

if (n == 1 && ln.size() > 1) { // remove the last node

ln[ln.size() - 2]->next = nullptr;

return head;

} else if (n == ln.size()) { // remove the first node

return head->next;

}

ln[ln.size() - n - 1]->next = ln[ln.size() - n + 1]; // remove the middle node

return head;

}

};