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

一.题目描述
NC53删除链表的倒数第n个节点
题目链接:
https://www.nowcoder.com/practice/f95dcdafbde44b22a6d741baf71653f6?tpId=188&&tqId=38587&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking
给定一个链表，删除链表的倒数第 nn 个节点并返回链表的头指针
例如，给出的链表为: 1->2->3->4->5，n=2。删除了链表的倒数第n个节点之后,链表变为1->2->3->5
二.算法(模拟)
一种很简单的方法是，我们首先从头节点开始对链表进行一次遍历，得到链表的长度L。随后我再从头节点开始对链表进行一次遍历，当遍历到L-n+1个节点时，它就是我们删除的节点。

对于单链表删除我们可以看上图，只要“跃过”要删除的结点那么就可以实现删除了，下面之间给出完整代码：

class Solution {
public:
    //求链表的长度
    int len(ListNode* head){
        int s=0;
        while(head!=NULL){
            s++;
            head=head->next;
        }
        return s;
    }
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* pre=head;
        int k=len(pre)-n;
        //要是之间是删除的是头节点 直接指针后移
        if(k==0){
            return head->next;
        }
        for(int i=0;i<k-1;i++){
            pre=pre->next;
        }
        //越过删除的结点
        pre->next=pre->next->next;
        return head;
    }
};

时间复杂度：O(n)对链表的所以元素遍历一遍
空间复杂度：O(1)不需要额外空间
优缺点：求链表长度需要遍历整个数组，但是时间复杂度低，容易实现。
三.算法(双指针)
利用算法二是肯定的可以解决问题的，但题目要求我们一次遍历解决问题，那我们就可以使用双指针来解决问题了。我们可以设想假设设定了双指针p和q的话，当q指向末尾的 NULL，p 与 q 之间相隔的元素个数为 n 时，那么删除掉p的下一个指针就完成了要求。
(1)设置虚拟节点Head指向 head
(2)设定双指针p和q，初始都指向虚拟节点Head
(3)移动q，直到p与q之间相隔的元素个数为n
(4)同时移动p与q，直到q指向的为NULL
(5)将p的下一个节点指向下下个节点

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=delNode->next;
        delete delNode;//删除多于结点

        ListNode* retNode=Head->next;
        delete Head;//删除多余节点
        return retNode;

    }
};

时间复杂度：O(n)对链表所有元素遍历一遍
空间复杂度：O(1)没有使用额外的空间
优缺点：只用了一次遍历，但是实现起来复杂