[2020.10.14] 删除链表倒数第n个节点

类似于环链，我们需要两个运动员，但这次其中一个需要比另一个快n步，而这次是直跑道，快的运动员跑道终点的前面时，慢的运动员就到了我们需要的位置的前面了。

当然搞一个容器存也可以，这个更容易理解，但时间不允许啊。

下面代码包括了一些不需要的处理，有相关说明：

/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param n int整型 
     * @return ListNode类
     */
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // write code here
        if (head == nullptr || head->next == nullptr) {
            return nullptr;
        }
        // 类似判断环形链
        // 建立两个节点，一个比另一个快n步
        // 如果快的节点的下一个节点指向了nullptr， 则慢的节点是需要删除的节点的前一个节点
        auto fast = head;
        auto slow = head;
        while (fast->next != nullptr) {
            if (n > 0) {
                n--;
            } else {
                slow = slow->next;
            }
            fast = fast->next;
        }
        // 如果循环完成, n>0
        // n == 1，则删除的结点为第一个
        // 其他数字，则删除的节点不存在，这种情况在本题目中不会出现；
        if (n > 0) {
            if (n == 1) {
                return head->next;
            }
            return head;
        }

        // 结束循环则找到，错误情况到这基本不会出现，除非传入不是直链
        auto will_delete_node = slow->next;
        slow->next = will_delete_node->next;
        delete will_delete_node;

        // 修改的是指针，则对应的操作已经完成，返回头指针
        return head;
    }
};