用于排序包含 0、1 和 2 的链表的 JavaScript 程序

---

在本教程中，我们将学习用于排序包含 0、1 和 2 的链表的 JavaScript 程序。排序算法对于任何编程语言都是必不可少的，JavaScript 也不例外。排序包含 0、1 和 2 的链表是一个常见问题，开发人员在编码面试和实际应用中都会遇到。

因此，让我们深入研究如何使用 JavaScript 编程对包含 0、1 和 2 的链表进行排序。

什么是排序？

排序是按特定顺序（升序或降序）排列元素的过程。它是计算机科学中的一项基本操作，在现实场景中有很多应用。排序算法用于组织数据以进行高效搜索，减少冗余，并优化空间和时间复杂度。

以下是一些 JavaScript 中排序的示例

示例 1 − 按升序排序数字数组

Input: ar[]= [5, 3, 8, 1, 2, 9]
Output: [1, 2, 3, 5, 8, 9]

示例 2 − 按字母顺序排序字符串数组

Input: ['apple', 'banana', 'orange', 'grape']
Output: ['apple', 'banana', 'grape', 'orange']

什么是链表？

链表是一种线性数据结构，由通过指针链接在一起的节点组成。每个节点包含一个数据元素和对列表中下一个节点的引用。链表通常用于动态数据结构，其中数据的规模会频繁变化。

问题陈述

目标是排列和显示一个包含 0、1 和 2 的有序链表。让我们通过示例来理解它

示例

Input: 1 -> 1 -> 2 -> 0 -> 2 -> 0 -> 1 -> NULL 
Output: 0 -> 0 -> 1 -> 1 -> 1 -> 2 -> 2 -> NULL
Input: 1 -> 1 -> 2 -> 1 -> 0 -> NULL 
Output: 0 -> 1 -> 1 -> 1 -> 2 -> NULL 

排序包含 0、1 和 2 的链表的算法

使用计数排序算法对包含 0、1 和 2 的链表进行排序的步骤：

步骤 1 − 定义一个函数 sortList(head)，它以链表的头节点作为输入。

步骤 2 − 初始化一个大小为 3 的计数数组 count[]，所有元素都为 0。

步骤 3 − 遍历链表，并将节点数据在计数数组中相应索引的计数递增。

步骤 4 − 再次遍历链表，并用计数大于 0 的最低索引值替换节点数据。

步骤 5 − 对于每次替换，递减节点数据的计数。

步骤 6 − 打印排序前和排序后的链表。

现在让我们尝试通过一个示例来理解上述算法，在这个示例中，我们将使用 JavaScript 实现此算法。

示例

下面的 JavaScript 程序使用计数排序算法对包含 0、1 和 2 的链表进行排序。该算法首先计算列表中 0、1 和 2 的频率，然后根据每个值的计数更新列表中节点的值。

/* Link list node */
class Node {
   constructor(data) {
      this.data = data;
      this.next = null;
   }
}
class LinkedList {
   constructor() {
      this.head = null;
   }
   push(new_data) {
      const new_node = new Node(new_data);
      new_node.next = this.head;
      this.head = new_node;
   }
   printList() {
      let currentNode = this.head;
      let value = "";
      while (currentNode !== null) {
         value += currentNode.data + " -> ";
         currentNode = currentNode.next;
      }
      console.log(value + "null");
   }
   sortList() {
      const count = [0, 0, 0]; // Initialize count of '0', '1' and '2' as 0
      let ptr = this.head;
      while (ptr !== null) {
         count[ptr.data] += 1;
         ptr = ptr.next;
      }
      ptr = this.head;
      let i = 0;
      while (ptr !== null) {
         if (count[i] === 0) {
            ++i;
         } else {
            ptr.data = i;
            --count[i];
            ptr = ptr.next;
         }
      }
   }
}
const linkedList = new LinkedList();
linkedList.push(0);
linkedList.push(1);
linkedList.push(0);
linkedList.push(2);
linkedList.push(1);
linkedList.push(1);
linkedList.push(2);
linkedList.push(1);
linkedList.push(2);
console.log("Before sorting:");
linkedList.printList();
linkedList.sortList();
console.log("After sorting:");
linkedList.printList();

结论

总的来说，上述 Javascript 程序演示了一种使用计数技术对仅包含 0、1 和 2 的链表进行排序的有效方法。该算法的时间复杂度为 O(n)，空间复杂度为 O(1)，使其成为此特定排序问题的最佳解决方案。