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

删除链表的倒数第n个节点
给定一个链表，删除链表的倒数第 nn 个节点并返回链表的头指针

示例
输入：{1,2},2
返回值：{2}

方法一 存入集合模拟

将所有元素存入vector中获取倒数第n的位置将其转换，但倒数第一个和正数第一个需要特判一下

代码

 ListNode* removeNthFromEnd(ListNode* head, int n) {
        // write code here
        ListNode *now = head;
        vector<ListNode*> arr;
        while(now){    //遍历一遍链表
            arr.push_back(now);
            now = now->next;
        }
        if(n == 1){ //特判如果是倒数第一个
            if(arr.size() > 1){ //如果链表长度大于1
                arr[arr.size() - 2]->next = NULL;
            }else return NULL; //如果等于一则删除列表就为空
            return head;
        }
        if(n == arr.size()){    //如果是删除第一个则直接返回第一个的下一个
            return arr[1];
        }
        int s = arr.size() - n;
        arr[s - 1]->next = arr[s + 1];
        return head;
    }

时间复杂度 O(n) 遍历一遍链表
空间复杂度 O(n) vector存储了整个链表开辟O(n)的空间

方法二 双指针

创建两个listNode 分别执行 当前遍历到的结点和当前结点的倒数第n + 1 个点结点，但不理完后即可直接更新，和方法一一样需要特判一下n是最后一个还是第一个。

代码

ListNode* removeNthFromEnd(ListNode* head, int n) {
        // write code here
        ListNode *now = head;
        ListNode *ls = head, *rs = head;
        int cnt = 0;
        int sum = 0;
        while(now){    //遍历链表
            sum ++;
            now = now->next;
            if(cnt > n){    //维护两个指针的距离为n + 1
                cnt --;
                ls = ls->next;
            }
            cnt ++;
        }
        if(sum == n){    //如果是删除第一个
            return head->next;
        }else if(n == 1){    //删除最后一个
            ls->next = NULL;
        }else 
            ls->next = ls->next->next;

        return head;
    }

时间复杂度: O(n) 遍历整个链表
空间复杂度: O(1) 使用了若干个变量