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

在C++中，链表是一种常见的数据结构，它可以实现动态的数据存储。对于0、1、2形式的链表，我们可以采用不同的排序算法进行排序，本文将介绍如何使用C++编写程序，对0、1、2形式的链表进行排序。

一、链表的定义和创建

链表是一种非线性数据结构，它由节点组成，每个节点包含两个部分：数据域和指针域。指针域指向下一个节点，最后一个节点的指针域指向NULL。

定义链表节点的结构体如下：

//链表的节点
struct ListNode{
    int val; //数据域
    ListNode *next; //指针域
    ListNode(int x) : val(x), next(NULL) {} //构造函数
};

创建链表的方法很多，本文介绍两种方法：

方法一：头插法创建链表

头插法是指，在链表头插入节点，插入顺序和数据顺序相反，即后插入的数据在前面。具体实现如下：

//头插法创建链表
ListNode* createList(vector<int> &nums){
    ListNode *head = new ListNode(-1);
    for(int i = 0; i < nums.size(); i++){
        ListNode *node = new ListNode(nums[i]);
        node->next = head->next;
        head->next = node;
    }
    return head->next;
}

例如，要创建一个链表1->2->3->4，代码如下：

vector<int> nums = {1,2,3,4};
ListNode *head = createList(nums);

方法二：尾插法创建链表

尾插法是指，在链表尾插入节点，插入顺序和数据顺序相同，即后插入的数据在末尾。具体实现如下：

//尾插法创建链表
ListNode* createList(vector<int> &nums){
    ListNode *head = new ListNode(-1);
    ListNode *tail = head;
    for(int i = 0; i < nums.size(); i++){
        ListNode *node = new ListNode(nums[i]);
        tail->next = node;
        tail = tail->next;
    }
    return head->next;
}

例如，要创建一个链表1->2->3->4，代码如下：

vector<int> nums = {1,2,3,4};
ListNode *head = createList(nums);

二、对0、1、2形式的链表进行排序

方法一：计数排序

计数排序是一种简单且高效的排序算法，在本例中可以用来对0、1、2形式的链表进行排序。

计数排序的思路是，先统计序列中0、1、2出现的次数，然后按照次数的顺序依次输出每个元素，即可完成排序。

具体实现如下：

ListNode* sortList(ListNode* head) {
    int count[3] = {0,0,0};
    ListNode *p = head;
    while(p){
        count[p->val]++;
        p = p->next;
    }
    p = head;
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < count[i]; j++){
            p->val = i;
            p = p->next;
        }
    }
    return head;
}

例如，要对链表1->0->2->0->1进行排序，代码如下：

vector<int> nums = {1,0,2,0,1};
ListNode *head = createList(nums);
head = sortList(head);

方法二：快速排序

快速排序是一种常用的排序算法，它的核心思想是分治法。在本例中，可以用快速排序来对链表进行排序。

快速排序的思路是，在序列中选择一个元素作为基准值，将序列划分为两部分，一部分比基准值小，一部分比基准值大，然后对这两部分分别递归进行快速排序，最终整个序列就被排序了。

具体实现如下：

//获取链表的中间节点
ListNode* getMidNode(ListNode* head){
    ListNode *slow = head;
    ListNode *fast = head->next;
    while(fast != NULL && fast->next != NULL){
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

//合并两个有序链表
ListNode* merge(ListNode* left, ListNode* right){
    ListNode *merged = new ListNode(-1);
    ListNode *p = merged;
    while(left && right){
        if(left->val < right->val){
            p->next = left;
            left = left->next;
        }
        else{
            p->next = right;
            right = right->next;
        }
        p = p->next;
    }
    if(left){
        p->next = left;
    }
    if(right){
        p->next = right;
    }
    return merged->next;
}

//快速排序
ListNode* quickSort(ListNode* head){
    if(head == NULL || head->next == NULL){
        return head;
    }
    //选择第一个节点作为基准值
    ListNode *pivot = head;
    head = head->next;
    pivot->next = NULL;
    //将序列划分为两部分
    ListNode *left = new ListNode(-1);
    ListNode *right = new ListNode(-1);
    ListNode *p = head;
    ListNode *l = left;
    ListNode *r = right;
    while(p){
        if(p->val < pivot->val){
            l->next = p;
            l = l->next;
        }
        else{
            r->next = p;
            r = r->next;
        }
        p = p->next;
    }
    //递归排序左右两部分
    left = quickSort(left->next);
    right = quickSort(right->next);
    //合并排好序的链表
    ListNode *merged = merge(left, right);
    //连接基准值节点
    p = merged;
    while(p->next){
        p = p->next;
    }
    p->next = pivot;
    pivot->next = merge(left, right);
    return merged;
}

例如，要对链表1->0->2->0->1进行排序，代码如下：

vector<int> nums = {1,0,2,0,1};
ListNode *head = createList(nums);
head = quickSort(head);

结论

本文介绍了两种方法来对0、1、2形式的链表进行排序：计数排序和快速排序。通过实现这两种算法，可以更好地理解链表和排序算法的基本原理。需要注意的是，在实际应用中，不同的排序算法可能有不同的优缺点，需要根据实际情况选择合适的算法。