题解 | #删除链表的倒数第n个节点#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param n int整型 
     * @return ListNode类
     */
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // write code here
        ListNode newhead(-1);
        ListNode* newheadptr = &newhead;
        newheadptr->next = head;
        vector<ListNode*> addr;
        while (newheadptr!=nullptr) {
            addr.push_back(newheadptr);
            newheadptr = newheadptr->next;
        }
        ListNode *pre_ptr = addr[addr.size()-n-1];
        if (n==1) {
            ListNode *after_prt = nullptr;
        }
        ListNode *after_prt = addr[addr.size()-n+1];
        pre_ptr->next = after_prt;
        return newhead.next;
    }
};

解题思想：借助哈希表

时间复杂度O（N），空间复杂度O（N）；

1.新建一个vector，按顺序把节点放进去

2.根据vector索引，得到对应要删除的前一个节点，后一个节点，并把节点地址赋值给对应的pre，after变量

3.让pre下一个地址直接指到after变量，越过要删除变量的地址，从而成功删除