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

题目：

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例1

示例1
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例2
输入：head = [1], n = 1
输出：[]

示例3
输入：head = [1,2], n = 1
输出：[1]

自行解答：

算法思路：

其实算法是链表中常用的经典算法，双指针或快慢指针

1：初始化2个指针，分别是first 和second

2：快指针先移动，在等待n回合之后，慢指针和快指针一起开始移动，当快指针移 动到最后一个元素时间，移动停止

3：开始删除节点（n是指链表的倒数第n个节点）

3.1：如果在循环结束时间，慢指针还在头结点，且n大于循环的次数，此时需要删除头结点

3.2：如果在循环结束时间，慢指针还在头结点，且n等于循环的次数，此时慢指针的下一个就是需要删除的元素

3.3：慢指针离开头结点的时候，直接删除满指针后面的元素即可

4：返回删除节点后的头结点

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) {}
};
void deleteMiddleNode(const ListNode *firstPointer, ListNode *secondPointer) {
    ListNode *beforeRemove = secondPointer;
    ListNode *needRemove =  secondPointer->next;
    ListNode *afterRemove;
    if(needRemove == firstPointer){
        beforeRemove->next = nullptr;
    } else {
        afterRemove = needRemove->next;
        beforeRemove->next =afterRemove;
    }
}

ListNode* removeNthFromEnd(ListNode* head, int n) {

    if(n==1 && head->next == nullptr){
        return nullptr;
    }
    //1：初始化快慢指针
    ListNode *firstPointer;
    firstPointer = head;//快指针
    ListNode *secondPointer;
    secondPointer = head;//慢指针
    ListNode * result = head;
    int count = 0;
    //2：移动快慢指针
    while (firstPointer->next!= nullptr){
        if(count >= n){
                secondPointer = secondPointer->next;
        }
        firstPointer = firstPointer->next;
        count++;
    }
    if(secondPointer == head ){
      //3.1在慢指针还在头结点的前提下，移除头结点  
      //删除头节点
        if(n>count){
            result = head->next;
        }
        //3.2在慢指针还在头结点的前提下，移除中间结点  
        //删除中间节点的
        if(n==count){
            deleteMiddleNode(firstPointer, secondPointer);
        }
    } else{
      //3.3在慢指针已经移动到中间节点了，删除慢指针后面的节点
        deleteMiddleNode(firstPointer, secondPointer);
    }
  //4：返回删除节点之后的头结点
    return result;
}

int main() {
    ListNode l1(1);
    ListNode l2(2);
    ListNode l3(3);
    ListNode l4(4);
    ListNode l5(5);
    l1.next = &l2;
    l2.next = &l3;
    l3.next = &l4;
    l4.next = &l5;
    ListNode *result = removeNthFromEnd(&l1,2);
    cout << "result head"<<result->val<<endl;
    return 0;
}

算法分析：

时间复杂度：O(N)，N是链表的长度，因为只循环了一趟

空间复杂度：O(1)，只使用了有限变量，未使用额外的空间

官方解答：

官方思路1：

采用栈的结构实现，即遍历一遍链表，顺序遍历时每个元素都入栈，当出栈时，开始计数，删除出栈的第n个元素即可

采用栈算法实现时，算法的时间复杂度为O(N)，N是链表的长度，空间复杂度也是O(N)，因为采用了栈来额外存储，具体代码如下：

 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;
    }

官方思路2：

采用也是快慢指针来实现，但是使用了一个小的技巧，即在入参传入之后，重新给链表指定个一个头结点dummy，这样就避免了，删除头结点的时候的场景识别，我们永远返回的头结点都是dummy.next，非常使用的小技巧，时间空间复杂度和自行解答中的一样

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;
}