algorithm - 删除链表中的第 10000 个节点

Question

我有一个 n 个节点的链表，我想删除第 k 个节点并显示其中的元素。如果 n 的值相对较小并且问题的复杂性不是问题，这很容易。

问题是当我在链表中​​有 n 个节点，其中 n >=200000，我想删除一个值也相对较大的节点(比如 k=150000)。

这个问题的正常解决方案是遍历整个链表并删除一个节点(解决方案的复杂度为 O(n) )，虽然它是直接且简单的解决方案，但需要更多时间。这个问题的其他解决方案可以有 2 个指针，但这仍然不是最佳解决方案。

我正在寻找最佳解决方案并在最短时间内提供结果。

希望我的问题很清楚。需要一些帮助..

Answer 1

使用SkipList概念。

这就像使用Express 车道或公路，以最快的速度到达所需的节点(通过选择最小的遍历长度)。

您需要创建多个层，以便您可以毫不犹豫地跳过一些节点。

TC: 与二叉搜索树 O(log n) 相同的平均运行时间。

不需要对给定的链表进行复杂的重组。