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) 以错误的顺序替换元素]