用于对以交替升序和降序排序的链表进行排序的Javascript程序

原文:https://www . geesforgeks . org/Javascript-排序程序-链接列表-排序-交替-升序和降序/

给定一个链表。链表是以交替的升序和降序排列的。高效地对列表进行排序。

示例:

Input List: 10 -> 40 -> 53 -> 30 -> 67 -> 12 -> 89 -> NULL
Output List: 10 -> 12 -> 30 -> 40 -> 53 -> 67 -> 89 -> NULL
Input List: 1 -> 4 -> 3 -> 2 -> 5 -> NULL
Output List: 1 -> 2 -> 3 -> 4 -> 5 -> NULL


简单解决方案:

方法:基本思路是应用于链表上的合并排序。
本文讨论实现:链表合并排序。

复杂度分析:

• 时间复杂度:链表的合并排序需要 O(n log n)时间。在合并排序树中，高度是 log n。对每个级别进行排序将花费 O(n)个时间。所以时间复杂度为 O(n ^ log n)。


• 辅助空间: O(n log n)，在合并排序树中高度为 log n，存储每一级将占用 O(n)空间。所以空间复杂度为 O(n ^ log n)。

高效解决方案:
进场:

1. 分开两个列表。


2. 以降序颠倒顺序


3. 合并两个列表。

图示:

以下是上述算法的实现:

java 描述语言

输出:

Given Linked List is
10 40 53 30 67 12 89
Sorted Linked List is
10 12 30 40 53 67 89


复杂度分析:

• 时间复杂度: O(n)。
  需要一次遍历来分离列表并反转它们。排序列表的合并需要 O(n)个时间。


• 辅助空间: O(1)。
  不需要额外空间。

请参考整篇文章，排序一个升序和降序交替排序的链表？了解更多详情！