将一个STL列表分割？

Question

我有一个循环链表，长这样：

4 -> 3 -> 2 -> 5 -> 0 -> 1 -> 开始

我想把这个链表分成两个部分，反转其中一个部分，然后重新连接。类似这样：

分割，O(1) 操作 4 ** 3 -> 2 -> 5 ** 0 -> 1 -> 开始

反转，O(n) 操作 0 ** 3 -> 2 -> 5 ** 4 -> 1 -> 开始

重新连接，O(1) 操作 0 -> 3 -> 2 -> 5 -> 4 -> 1 -> 开始

STL似乎没有循环链表，但我希望可以用(forward) list表示列表。这需要： * 将列表拆分为子列表的方法 * 合并列表的方法

使用std::list::splice合并子列表应该很容易，并且应该是O(1)操作。太好了！

然而，我找不到一个好的O(1)方法来将列表拆分为子列表。一种方法是使用迭代器，但我认为在我的情况下不适用，因为子列表在列表的末尾结束，并在列表的开头继续。

有没有有效的方法使用STL实现此算法？还是我应该放弃并编写自己的循环链表库？

谢谢！

- John Saxton

---

如果你的总操作是O(N)，为什么你想让你的分割操作变成O(1)？根据这个链接，目前没有标准实现循环链表的方法。https://dev59.com/_XNA5IYBdhLWcg3wdtv5 - Abhishek Bansal

最终，我希望尽可能地使我的程序运行速度快。O(N)的分割 + O(N)的反转比起O(1)的分割 + O(N)的反转要慢。另外，我相当确定我可以总是反转最短的子列表，所以希望在那种情况下N很小。 - John Saxton

这是用于TSP吗？您可能需要使用两级树而不是链表，这将减少运行时间到O(sqrt(n))，而不会像二叉树（O(log(n)）那样有大的常数因子。 - David Eisenstat

@JohnSaxton 我认为在链表中，分割操作不可能是O(1)的操作。这是因为你首先需要到达“分割节点”，然后再转移“下一个”指针。这个“到达”操作是一个O(N)的操作。 - Abhishek Bansal

@JohnSaxton，对于分割，O(0)怎么样？不要分割列表，只需使用子列表开头的常量迭代器列表进行逻辑分割，然后在到达下一个迭代器时停止 :) 对于反转，您可以在中心轴周围进行反射交换（如果所选子列表的大小为奇数，则不存在中心轴）。 - Khaled.K

@JohnSaxton：“O（N）分割+ O（N）...会更慢”，例如N + N与1 + 100 * N。 - kilotaras

Answer 1

我不确定这是否有帮助，但是我会尽力：

template<typename I>
void inner(I b, I e)
{
    std::reverse(b, e);  // l = {4 5 2 3 0 1}
}

template<typename L, typename I>
void outer(L& l, I b, I e)
{
    l.splice(l.begin(), l, e, l.end());  // l = {0 1 4 3 2 5}
    std::reverse(l.begin(), b);          // l = {4 1 0 3 2 5}
}

int main ()
{
    std::list<int> t, l{4, 3, 2, 5, 0, 1};
    std::cout << l << std::endl;

    auto b = l.begin(), e = l.begin();
    std::advance(b, 1);
    std::advance(e, 4);
    bool in = true;

    in ? inner(b, e) : outer(l, b, e);
    std::cout << l << std::endl;
}

有两个选项：

• 翻转列表的内部部分（3 2 5）
• 翻转列表的外部部分（0 1 -> 4）

你可能想要翻转较短的那个，但是你需要计算，这是线性时间的。我为这两个任务编写了两个单独的函数inner,outer。 inner非常简单（仅仅是一个包装器）并且按预期工作。然而，outer会使列表处于等效于期望模一些旋转（循环移位）的状态。如果您正在建模一个循环列表，那么这应该没问题。但是，如果您希望输出与您的示例完全相同，则必须再次计数以找到正确的旋转点。我会避免这样做，因为它是线性时间的。

请注意，实际上不需要拆分，因为翻转是原地进行的。此外，操作

l.splice(l.begin(), l, e, l.end());

时间复杂度是常数级的。

查看实时示例。

- iavr