类似于环链,我们需要两个运动员,但这次其中一个需要比另一个快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;
    }
};