删除链表中的第 10000 个节点
Delete a 10000th node in linked list
我有一个n个节点的链表，我想删除第k个节点并显示其中的元素。如果 n 的值相对较小并且问题的复杂性不是问题，这很容易。
问题是当我在链表中有 n 个节点，其中 n >=200000，我想删除一个值也相对较大的节点（比如 k=150000）。
这个问题的正常解决方案是遍历整个链表并删除一个节点（解决方案的复杂度为 O(n) ），虽然它是直接且容易的解决方案但需要更多时间。这个问题的其他解决方案可以有 2 个指针，但这仍然不是最佳解决方案。
我正在寻找一种最佳的解决方案，它可以在最短的时间内提供结果。
希望我的问题很清楚。需要一些帮助..
你有一个链表，所以你的访问是 O(n)..
我看到两个选择：更改您的容器或使用辅助容器来加速直接访问（增加您的 space 复杂性）..
你不会找到一个对所有处理都具有 O(1) 复杂度的神奇容器。
在标准链表中，没有办法（没有额外的指针）快速访问列表后面的元素，因为对所述元素的唯一引用出现在它前面的元素中。
如果您知道经常需要访问索引已知的元素，那么最好只使用数组。 （虽然重新阅读问题，这仍然对删除元素没有任何好处）
使用SkipList概念。
这就像使用Express车道或公路，以最快的速度到达所需的节点（通过选择最小的遍历长度）。
您需要创建多个图层，以便您可以毫不犹豫地跳过一些节点。
TC: 与二叉搜索树 O(log n) 相同的平均 运行 时间。
不需要对给定的链表进行复杂的重组。
我有一个n个节点的链表，我想删除第k个节点并显示其中的元素。如果 n 的值相对较小并且问题的复杂性不是问题，这很容易。
问题是当我在链表中有 n 个节点，其中 n >=200000，我想删除一个值也相对较大的节点（比如 k=150000）。
这个问题的正常解决方案是遍历整个链表并删除一个节点（解决方案的复杂度为 O(n) ），虽然它是直接且容易的解决方案但需要更多时间。这个问题的其他解决方案可以有 2 个指针，但这仍然不是最佳解决方案。
我正在寻找一种最佳的解决方案，它可以在最短的时间内提供结果。
希望我的问题很清楚。需要一些帮助..
你有一个链表，所以你的访问是 O(n).. 我看到两个选择：更改您的容器或使用辅助容器来加速直接访问（增加您的 space 复杂性）.. 你不会找到一个对所有处理都具有 O(1) 复杂度的神奇容器。
在标准链表中，没有办法（没有额外的指针）快速访问列表后面的元素，因为对所述元素的唯一引用出现在它前面的元素中。
如果您知道经常需要访问索引已知的元素，那么最好只使用数组。 （虽然重新阅读问题，这仍然对删除元素没有任何好处）
使用SkipList概念。
这就像使用Express车道或公路，以最快的速度到达所需的节点（通过选择最小的遍历长度）。
您需要创建多个图层，以便您可以毫不犹豫地跳过一些节点。
TC: 与二叉搜索树 O(log n) 相同的平均 运行 时间。
不需要对给定的链表进行复杂的重组。