解题思路

此题可以使用快慢指针解法。 对于有关链表的删除操作一类题，记住一个小技巧就是新建一个假头，这样可以避免复杂的边界判断。

1. 新建一个假头ans，并使其后继结点为head；
2. 新建慢指针slow指向ans，快指针fast指向head；
3. 先让快指针fast后移n个位置，之后快慢指针一起向后移动直至fast指针指向空。 则此时slow指向的节点即为需要删除的节点。只需进行slow->next = slow->next->next即可。 最后返回答案，ans->next。

代码

/**
 * 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* ans = new ListNode(0);//新建假头节点，避免边界判断
        ans -> next = head;//假头节点的后继结点为真头结点
        ListNode* slow = ans;//慢指针
        ListNode* fast = head;//快指针
        int count = 0;//计数器
        while(fast!=nullptr){//快指针先后移n次
            fast = fast->next;
            count++;
            if(count>=n)  break;
        }
        while(fast!=nullptr){//快慢指针一起移动
            fast = fast->next;
            slow = slow->next;
        }
        slow -> next = slow->next->next;//删除目标节点
        return ans->next;//返回答案
    }
};

复杂度分析

时间复杂度： O(N)。其中N为链表长度，因为我们需要遍历整个链表。

空间复杂度： O(1)。只需常数个临时空间即可。