c++ - 链表中的高效“插入”功能

Question

在一次采访中，我被要求为链表编写一个插入函数，这样在插入后，与插入元素相比，插入元素头部的元素应该更大，而尾部的元素应该更小。

我在我的代码中实现了以下步骤：

1. 最初按降序对链表进行排序。
2. 获取元素。
3. 以这样的方式插入元素，即使插入后链接列表也将按降序排列。

但有人告诉我，我的方法效率不高。

请让我知道是否有有效的方法来实现相同的目标。

Answer 1

排序是一种O(n log n)操作。如果您仔细阅读问题，他们从不说应该对列表进行排序，所以不要进行排序操作。相反，您应该做的是从一个仅包含您的元素的新列表开始，然后对于原始列表的每个元素，将其附加到前面（如果大于新元素）或后面。