题目

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

难度中等1594

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

进阶：你能尝试使用一趟扫描实现吗？

 大概思路

1.  设置p，q两个指针（初始化为head）
2. p先向后移动n个位置
3. 然后 p、q 指针一起向后移动 ，直到p指向链表最后一个结点（此时q指针指向需要被删除结点的前一个结点）
4. 删除q的后继结点

注：需要考虑删除头结点的情况

代码

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *q=head,*p=head,*t=head->next;
        if(head==NULL)
        {
            return head;
        }
        while(n--&&p->next!=NULL)  //p指针向后移动n位
        {
            p=p->next;
        }
        if(n!=-1)   //删除头结点
        {
            t=head;
            head=head->next;
            delete t;
            return head;
        }
        while(p->next!=NULL)   //p指针和q指针一起向后移动，直到p指向最后一个结点
        {
            q=q->next;p=p->next;
        }
        t=q->next;
        q->next=t->next;
        delete t;
        return head;
    }
};