删除最后第N个

Question

如果我的链表有 10000 个节点，那么如何在不一次又一次遍历的情况下删除最后一个节点中的第 N 个节点？

我一次又一次地遍历链表以找到长度，然后遍历并从最后一个删除，这导致每次的复杂度都是 O(n)

Answer 1

向前扫描列表，同时倒退列表。一旦到达末尾，向后扫描 n 次，同时不反转列表，并将指针保存到从最后一个节点开始的第 n 个节点。然后继续向后扫描，同时取消反转列表以恢复它。返回指向最后一个节点的第 n 个节点的指针。这只需要遍历两次列表。