有效地重新排序链表

Question

我在一次采访中得到了这个问题，如下：

如果我有这样的链表，

1->2->3->4->5->6

我必须将其转换为

1->6->2->5->3->4

如果是这样的话，

1->2->3->4->5->6->7

我必须将其转换为

1->7->2->6->3->5->4

而且，最重要的是，我必须修改原始链表，无法创建新的链表。我想到了一个递归。但是，我真的解决不了。此外，他们限制了这个函数只能有链表的头部。

Answer 1

这可以在线性时间内完成，O(n)并且通常在访谈期间（不幸的是）比解决方案的稳健性更重要。

您可以通过将原始列表拆分为两个大小相同（尽可能）的列表，然后反转第二个列表并逐个元素合并它们（第一个列表中的第一个元素，第二个列表中的第二个元素等）来实现。您不需要太多额外空间，因为您只需使用现有指针即可。

例如：

1->2->3->4->5->6

1->2->3 and 4->5->6 // after split, 3 points to null, 4 is head of second list
1->2->3 and 4<-5<-6 // after reorder
1->6->2->3 and 4<-5 // first phase of merge
1->6->2->5->3 and 4 // second phase of merge
1->6->2->5->3->4    // last phase of merge

您可以使用running pointer. 你用一个指针一次去一个节点，一个指针一次去两个节点来遍历列表。当较快的指针到达末尾（空）时，较慢的指针将在分裂之前，分裂前的节点必须指向空而不是下一个节点（在我们的例子中而不是 4）和下一个节点（4）成为第二个列表的头部。

反转第二个列表并合并是简单的指针交换。

请注意空指针:-)