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

删除链表的倒数第n个节点

1、题意重述

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

换句话说，即删除链表中指定位置的节点，并返回头指针。

2、思路整理

使用双指针的思想：

Step1:用两个指针p,q分别指向头节点。

Step2：将q指针向右移动，直到p和q指针之间元素的个数相差n。

Step3：同时移动p指针和q指针，直到q指向NULL。

Step4：此时p指针的next指向要删除的节点，执行删除操作即可。

Step5：返回头指针。

3、代码实现

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
     ListNode* Head =new ListNode(0);
        Head->next =head;
        ListNode* p=Head;//指向头节点
        ListNode* q=Head;
        for( int i=0;i<n+1;i ++ ){
            q=q->next;//q指针指向第n-1个节点
        }
        while(q){
            p=p->next;
            q=q->next;
        }
        ListNode* delNode=p->next;
        p->next=p->next->next;
        delete delNode;//删除

        ListNode* retNode=Head->next;
        delete Head;
        return retNode;
    }
};

4、复杂度分析

时间复杂度：对链表一次遍历，因此时间复杂度为$O(N)O(N)$。

空间复杂度：没有使用额外的内存地址空间，因此空间复杂度为$O(1)O(1)$。