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