能否在有序链表中以O(logn)时间插入元素？求非优先队列/BST的中位数解法

嘿，针对你的问题，我来梳理下可行的思路～

首先得明确核心瓶颈：你当前用普通双向链表插入元素，不管怎么优化遍历起点，最坏情况还是**O(n)**的时间复杂度，十万级数据下总时间就是O(n²)，肯定会慢。而且你排除了优先队列（堆）和BST，那我们可以从链表的变种结构入手，既保留链表的部分特性，又能把插入的时间复杂度降下来。

1. 跳表（Skip List）：平均O(logn)插入，高效维护中位数 #

跳表是有序链表的升级版本，通过给节点添加多层“索引”，让查找/插入操作可以跳过大部分节点，平均时间复杂度降到O(logn)，完全能hold住十万级数据。

具体实现时，你可以额外维护一个指向中位数节点的指针：

• 每次插入元素后，根据链表长度的奇偶变化（比如插入后总长度从偶数变奇数，或者奇数变偶数），结合插入位置和当前中位数的关系，调整中位数指针的位置（比如插入的元素比中位数小，且长度变奇数时，中位数可能左移；反之右移）。
• 这样每次获取中位数都是O(1)，累加总和就很轻松。

跳表的简化节点结构大概是这样：

struct SkipNode {
    long int data;
    vector<SkipNode*> forward; // 多层索引指针
    SkipNode(long int val, int level) : data(val), forward(level, nullptr) {}
};

实现的时候需要维护跳表的最大层数，以及头节点，插入时通过随机数决定新节点的层数，然后逐层更新索引。

2. 分块链表（Block Linked List）：O(√n)插入，实现更简单 #

如果觉得跳表实现有点麻烦，分块链表是个更轻量化的选择。我们把整个有序序列分成多个固定大小的块（比如块大小取√n，十万数据的话大概300左右），每个块内部用数组存储有序元素，同时维护每个块的大小、最小值、最大值，块之间用链表连接。

操作逻辑：

• 插入元素时，先通过遍历块链表（或者维护块的索引数组用二分查找）找到元素所属的块（根据块的min/max判断），然后在块的数组里用二分查找找到插入位置，移动元素插入。
• 如果块满了，就把块分裂成两个各占一半的新块，更新块链表。
• 中位数维护：记录中位数所在的块和块内的索引，每次插入后根据插入位置和总长度变化，调整这个记录即可，获取中位数也是O(1)。

分块链表的块结构示例：

struct Block {
    vector<long int> elements;
    int capacity; // 块的最大容量，比如设为300
    long int min_val, max_val;
    Block* next;
    Block(int cap) : capacity(cap), next(nullptr) {}
};

这种方案的插入时间是O(√n)，对于十万数据来说，每次插入最多操作300次，总时间是1e5*300=3e7，完全在可接受范围内。

对当前中心指针方案的小优化（治标不治本） #

如果暂时不想改结构，可以试试优化遍历起点：

• 插入元素时，先和head->data、tail->data、center->data比较：
  • 如果元素比head->data小，直接插头部；
  • 比tail->data大，直接插尾部；
  • 比center->data小，从center往前遍历找位置；
  • 比center->data大，从center往后遍历找位置。
    这种优化能减少平均遍历的节点数，但最坏情况还是O(n)，十万数据下可能还是不够快，只能作为临时过渡方案。

总结下来，跳表和分块链表都是不用优先队列/BST的可行方案，其中分块链表实现成本更低，足够解决你的十万级数据问题；跳表性能更优，适合更大规模的数据。

内容的提问来源于stack exchange，提问作者lws803