算法1(一次遍历)

解题思路

1. 因为会出现删除头结点的情况，比如[1] 1这种测试用例，不能让空指针nullptr还指向一个空指针，所以建立一个虚拟头结点dummy，从而可以避免这种情况。因为是一次遍历完成，所以要用到2个指针，如果是两次遍历，那么用1个指针就可以。
2. 定义的2个指针first和second一定是等于dummy的，这样虚拟头结点才能发挥作用，比如我一开始定义的first和second均指向了head，这样子dummy就没有存在的意义了，也相应地处理不了删除头结点的情况。
3. 算法思想：让second比first往前多走n步，这样当second指向最后一个节点的时候，(从结尾节点开始数，第n个节点距离结尾节点是n - 1步)，这时first距离second是n步的距离，first的下一个节点就是要删除的节点。
4. 第3步这样做的原因是，链表中删除节点k的操作都是让k的前驱节点的next指针指向k的后继结点，这样k就自然而然被删除了。大家可以细品一下。
5. 最后的return，一定要输入dummy->next，才可以AC。起初我以为return head也可以，是我太天真了，还是删除头结点的情况，如果return head，输出是1，但其实我们已经把head删除了，应该输出空。因为我们并没有真正的把head删掉，所以return head会返回1，我们只是改变了head前驱节点的next指针的指向，所以一定要返回return dummy->next。谨记！

代码

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(!head) return head;
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        // auto first = head, second = head; 
        auto first = dummy, second = dummy;
        for(int i = 0; i < n; i ++) second = second->next; 
        while(second->next != nullptr)
        {
            second = second->next;
            first = first->next;
        }

        first->next = first->next->next;

        return dummy->next;
    }
};

算法2(两次遍历)

解题思路

1. 像上述只遍历一次的话，需要两个指针，这里如果要只是用一个指针变量cur的话，就需要遍历2次。
2. 第一次遍历计算整个链表的长度len，第二次遍历通过len - n找到删除节点的位置，这里需要再开一个整型变量cnt来计算，当cnt == len - n的时候，删除cur指向的下一个节点，对应关系画个图会很明了。
3. 这里也要处理 删除头结点 的情况，如果链表的长度len和删除节点的位置n相等，说明该链表只有1个节点，也就是头结点，这时候直接return head->next，因为head头结点已经被我们省略了，直接返回head->next，也就是 空。

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) {
        int len = 0;
        for(auto cur = head; cur != NULL; cur = cur->next) len ++;

        if(len == n) return head->next;
        int cnt = 0;
        for(auto cur = head; cur != NULL; cur = cur->next)
        {
            cnt ++;
            if(cnt == len - n)
            {
                cur->next = cur->next->next;
                break;
            }
        }

        return head;
    }
};