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