对 0、1 和 2 的链表进行排序

链表是计算机科学和编程面试中使用的基本数据结构。它们提供了一种高效的方式来存储和访问顺序数据。链表的一个主要挑战是有效地对其元素进行排序。

与数组不同，链表只提供对节点的顺序访问。我们不能直接访问特定索引或交换元素，这使得某些排序算法（如快速排序或堆排序）难以在链表上实现。

一个常见的面试问题涉及对只包含节点值0、1和2的链表进行排序。目标是重新排列列表，使所有0首先出现，然后是1，最后是2。这依赖于在不使用任何额外存储的情况下，局部修改节点之间的链接以就地重新排序列表。

在本文中，我们将研究一种最优的O(n)算法，该算法在第一次遍历时计算0、1和2的数量。这使我们能够确定每个节点值的最终索引位置。在第二次遍历中，我们再次遍历列表并修改链接，根据计数将节点重新排列到正确的位置。

这展示了一种使用节点就地重新排序的有效链表排序技术。掌握此类算法是成功通过编码面试并展示对链表等数据结构的扎实掌握的关键。

什么是0、1和2的链表？

包含值为0、1和2的节点的链表表示排序链表的一种变体。具体来说，列表只包含3个可能的节点值，而不是整数、字符串等数据类型范围。

目标是重新排列列表，使得：

• 所有值为0的节点首先出现
• 接着是所有值为1的节点
• 最后，所有值为2的节点

例如，一个链表

2 -> 1 -> 0 -> 2 -> 1 -> 0

它将按以下方式排序

0 -> 0 -> 1 -> 1 -> 2 -> 2

主要限制是

• 列表必须就地排序，不能创建副本
• 只允许顺序访问节点
• 除了现有节点外，不能使用额外存储

这使得像合并排序或快速排序这样的通用排序算法难以实现，因为它们依赖于对元素的随机访问。

核心思想是遍历列表一次，以统计0、1和2的频率。这使我们能够确定每个节点值的最终位置。在第二次遍历中，我们重新排列节点之间的链接，根据计数将它们按正确的排序顺序放置。

这个问题展示了在给定固定可能值的情况下，就地排序链表的一些核心挑战和技术。它依赖于根据链表的特定结构和约束进行优化。

它的用途是什么？

仅包含0、1和2的链表在多个领域都有应用。一些例子包括：

• 在数字逻辑和电路设计中，链表可以表示仅包含低（0）、高（1）和浮动（2）信号的逻辑门和电路。对这些列表进行排序有助于简化和优化电路布局。
• 在操作系统中，进程优先级队列通常将进程分为三个级别：低、中和高优先级（0、1和2）。链表通常用于实现优先级队列，对其进行排序可以按优先级顺序调度进程。
• 在数据压缩中，霍夫曼编码用仅包含0和1的可变长度二进制代码表示符号。链表可以存储这些编码，排序有助于有效地打包代码。
• 在机器学习中，分类器将数据点分为0、1和2类。链表可以存储这些分类，排序可按预测类别排列点。
• 在数学和计算机科学中，三进制数字系统包含数字0、1和2。链表可以表示三进制数，排序可正确排列数字。

总的来说，任何数据可以分为3种不同类型或级别的地方，0、1和2的链表都提供了一种灵活高效的存储机制。能够有效地对其进行排序是各种算法和应用的关键。

算法及其 Python 实现

算法

1. 初始化计数变量
   • zeroCount = 0
   • oneCount = 0
   • twoCount = 0
2. 遍历链表并统计0、1、2的频率
   • 对于链表中的每个节点
     • 如果 node.value 为 0
       • zeroCount++
     • 如果 node.value 为 1
       • oneCount++
     • 如果 node.value 为 2
       • twoCount++
3. 再次遍历链表
   • 当前位置 = 0
   • 当 zeroCount > 0 时
     • 设置当前 node.value = 0
     • 递减 zeroCount
     • 移动到下一个节点
   • 当 oneCount > 0 时
     • 设置当前 node.value = 1
     • 递减 oneCount
     • 移动到下一个节点
   • 当 twoCount > 0 时
     • 设置当前 node.value = 2
     • 递减 twoCount
     • 移动到下一个节点
4. 列表现在已排序，0s 在前，然后是 1s，最后是 2s

该算法遍历链表两次。

第一次遍历统计频率。第二次遍历根据最终索引设置节点值并递减计数。

时间复杂度：O(N)

空间复杂度： O(1)

这种就地排序算法在不额外存储的情况下，最优地对包含0、1和2的链表进行排序。

输出

说明

1. 我们定义一个 Node 类来表示链表中的每个节点。它包含一个 value 字段和一个 next 字段，用于指向下一个节点。
2. LinkedList 类表示完整的链表。它有一个头节点和用于排序和打印列表的方法。
3. sortList() 方法首先遍历列表并统计其中0、1和2的数量。通过相应地递增 zero_count、one_count 和 two_count 变量来完成此操作。
4. 接下来，它再次遍历链表。现在，在每次迭代中
   • 如果 zero_count 大于 0，我们将当前节点的值设置为 0 并递减 zero_count。
   • 如果 one_count 大于 0，我们将当前节点的值设置为 1 并递减 one_count。
   • 如果 two_count 大于 0，我们将当前节点的值设置为 2 并递减 two_count。
5. 这通过根据值应处于的最终索引更改节点值来重新排序列表。
6. printList() 方法显示链表的当前状态。
7. 在主部分，我们创建一个包含2、1、0、2、1、0节点的示例链表。
8. 打印未排序的列表，然后调用 sortList()。
9. 最后，打印排序后的列表，现在它包含按0、0、1、1、2、2顺序排列的节点。

结论

总而言之，对值限制为0、1和2的链表进行高效排列可以通过线性时间复杂度O(n)和常数空间复杂度O(1)来实现。此方法依赖于计数排序算法，该算法对于此场景中的整数范围排序非常有效。通过统计频率并将值与位置关联，我们可以直接将元素放置在其位置。

由于链表不允许随机访问元素，计数有助于我们在初始遍历中确定每个值的最终位置。随后，我们可以再次遍历列表。顺序调整链接以将节点重新排序到它们所属的位置。这展示了一种为链表量身定制的排序技术，它利用了问题约束。在处理链式数据结构时，重新排列节点之间的链接以进行就地排序是一项技能。

此处演示的计数排序策略可以适用于涉及具有有限离散值集的链表或数组的排序任务。