algorithm - 使用已排序和反向排序的备用元素对链表进行排序

Question

我在一次采访中被问到这个问题。

列表看起来像这样。

a ₁ ->b _n ->a ₂ ->b _n-1 ... ->a _n ->b ₁ ->NULL

这样，a ₁ < a ₂ < ... < a _n

和

b ₁ < b ₂ < ... < b _n

面试官对我施加了以下限制：

1. 您必须对列表进行适当的排序，即不允许将一组元素的备用元素删除到单独的列表中。
2. 您必须以某种方式利用列表中的模式，而不是简单的排序算法。

在面试期间我无法想出解决方案，现在也是。:-(

编辑：用 C 编写代码来对这个单链表进行排序。

Edit2：有人告诉我，我可以从冒泡排序中借鉴一些想法并利用该模式。但它不应该是一个“幼稚”的短片。

我讨厌面试官施加人为限制，但嘿，工作就是工作:-)

Answer 1

“你必须对列表进行适当的排序”这个要求让我感到困惑。我原以为自然的解决方案是：

• 通过抖动列表中的“下一个”指针，创建两个列表。一个包含a，另一个包含b，颠倒过来。
• 在这两个列表上进行合并。

但我不确定第一步是否违反规则。正如我所理解的那样，它是“就地”，因为它不会复制节点或其数据，实际上它也不会移动任何数据。但它确实将替代元素删除到单独的列表中。

我无法立即想到如何将这两个步骤组合成一个通道。

[编辑：也许这里的“就地”意味着我们应该移动数据，而不是重新链接列表。在这种情况下，我认为问题更难：有效的就地合并排序在数组中已经足够痛苦了，而无需尝试（a）在链表上执行此操作，（b）使用错误顺序的替代元素]

Answer 2

为了保持它“就地”，您可以先将列表就地转换为

a ₁ -> ... -> a _n -> b ₁ -> ... -> b _n

通过遍历列表并将 b 元素一一移动到列表的末尾。

_{在此之后，您可以以“冒泡排序方式”将 a 元素一个接一个地向前移动，即向前扫描，直到在最初位于 b 1}之前的边界之后找到它们的位置。

但是我同意这个问题是相当人为的。