分析

• 本题的考点：双指针。

• 为了方便处理删除头结点的情况，这里使用虚拟头结点的技巧。

• 使用双指针p、q，刚开始都指向虚拟头结点dummy，先让指针q向后移动n+1个位置；之后p、q同时后移直到结点q指向空，此时让p->next = p->next->next，最后返回dummy->next即可。（可以以题目中例子看一下应该移动多少）。

代码

• C++

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {

        auto dummy = new ListNode(-1);
        dummy->next = head;
        auto p = dummy, q = dummy;

        for (int i = 0; i < n + 1; i++) q = q->next;
        while (q) p = p->next, q = q->next;

        p->next = p->next->next;

        return dummy->next;
    }
};

• Java

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {

        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode p = dummy, q = dummy;

        for (int i = 0; i < n + 1; i++) q = q.next;
        while (q != null) {
            p = p.next; q = q.next;
        }

        p.next = p.next.next;

        return dummy.next;
    }
}

时空复杂度分析

• 时间复杂度：$O(n)$，n为链表长度。

• 空间复杂度：$O(n)$，n为链表长度。