C++程序 对0、1、2形式的链表进行排序

给出一个由0、1和2组成的链表，请将其排序。

示例：

输入： 1->1->2->0->2->0->1->NULL
输出： 0->0->1->1->1->2->2->NULL

输入： 1->1->2->1->0->NULL
输出： 0->1->1->1->2->NULL

可以使用以下步骤来对给定的链表进行排序。

• 遍历该列表，并计算0、1和2的数量。让n1、n2和n3分别为计数。
• 再次遍历列表，用0填充前n1个节点，然后用1填充n2个节点，最后用2填充n3个节点。

下面的图形化解释以上过程：

下面是以上方法的实现：

// C++程序，用于对包含0、1或2的链表进行排序
#include <bits/stdc++.h>
using namespace std;

// 链表节点
class Node
{
    public:
    int data;
    Node* next;
};

// 用于对包含0、1和2的链表进行排序的函数
void sortList(Node *head)
{
    // 将“0”、“1”和“2”的计数初始化为0
    int count[3] = {0, 0, 0};
    Node *ptr = head;

    /* 计算“0”、“1”和“2”的总数
       count[0]将存储“0”的总数
       count[1]将存储“1”的总数
       count[2]将存储“2”的总数 */
    while (ptr != NULL)
    {
        count[ptr->data] += 1;
        ptr = ptr->next;
    }

    int i = 0;
    ptr = head;

    /* 假设count[0] = n1，count[1] = n2
       和count[2] = n3，
       现在从头节点开始遍历列表，
       1）用0填充列表，直到n1> 0
       2）用1填充列表，直到n2> 0
       3）用2填充列表，直到n3> 0 */
    while (ptr != NULL)
    {
        if (count[i] == 0)
            ++i;
        else
        {
            ptr->data = i;
            --count[i];
            ptr = ptr->next;
        }
    }
}

// 用于推入节点的函数
void push (Node** head_ref,
           int new_data)
{
    // 分配节点
    Node* new_node = new Node();

    // 将数据放入
    new_node->data = new_data;

    // 链接新节点的旧列表
    new_node->next = (*head_ref);

    // 将头指针移动到指向新节点
    (*head_ref) = new_node;
}

// 用于打印链表的函数
void printList(Node *node)
{
    while (node != NULL)
    {
        cout << node->data << " ";
        node = node->next;
    }
    cout << endl;
}

// 驱动程序
int main(void)
{
    Node *head = NULL;
    push(&head, 0);
    push(&head, 1);
    push(&head, 0);
    push(&head, 2);
    push(&head, 1);
    push(&head, 1);
    push(&head, 2);
    push(&head, 1);
    push(&head, 2);

    cout << "在排序之前的链表：";
    printList(head);

    sortList(head);

    cout << "排序之后的链表：";
    printList(head);

    return 0;
}

输出：

在排序之前的链表：2 1 2 1 1 2 0 1 0
排序之后的链表：0 0 1 1 1 1 2 2 2

时间复杂度： O(n)，其中n是链表中节点的数量。

辅助空间： O(1)