算法思路

关于链表的题目，由于链表数据结构的特殊性，当我们需要删除链表中某个结点的时候，我们需要找到它的前驱结点。我们返回链表时往往是返回的链表的头节点，因此我们还要想办法防止头节点被删除而无法返回链表的情况。对于本题，具体思路如下：

1. 为了防止头节点被删除，我们建立一个哑结点(dummy),使其指向最开始的头节点

2. 建立双指针first和second同时指向dummy，并先让first指针走k步

4. first和second指针同时向前走，直到first指针走到链表的最后一个节点停止，此时second的下一个结点就是我们需要删除的倒数第k个结点

5. 删除结点，并返回dummy的下一个结点

C ++代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        auto dummy = new ListNode(-1);
        dummy -> next = head;
        auto first = dummy, second = dummy;
        while (n --) first = first -> next;
        while (first -> next)
        {
            first = first -> next;
            second = second -> next;
        }
        second -> next = second -> next -> next;
        return dummy -> next;
    }
};