用c++写一个链表排序

以下是一个简单的链表排序程序：

#include <stdio.h>
#include <stdlib.h>

struct node {
    int data;
    struct node *next;
};

void insert(struct node **head, int val) {
    struct node *new_node = (struct node *) malloc(sizeof(struct node));
    new_node->data = val;
    new_node->next = NULL;
    if (*head == NULL) {
        *head = new_node;
    } else {
        struct node *p = *head;
        while (p->next != NULL) {
            p = p->next;
        }
        p->next = new_node;
    }
}

void print(struct node *head) {
    struct node *p = head;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

void swap(struct node *a, struct node *b) {
    int temp = a->data;
    a->data = b->data;
    b->data = temp;
}

void bubble_sort(struct node *head) {
    int swapped;
    struct node *p, *q = NULL;
    do {
        swapped = 0;
        p = head;
        while (p->next != q) {
            if (p->data > p->next->data) {
                swap(p, p->next);
                swapped = 1;
            }
            p = p->next;
        }
        q = p;
    } while (swapped);
}

int main() {
    struct node *head = NULL;
    insert(&head, 5);
    insert(&head, 1);
    insert(&head, 3);
    insert(&head, 2);
    insert(&head, 4);
    printf("Original list: ");
    print(head);
    bubble_sort(head);
    printf("Sorted list: ");
    print(head);
    return 0;
}

该程序使用冒泡排序对链表进行排序。在该程序中，我们首先定义了一个结构体`node`，其中包含一个`data`成员和一个`next`指针，指向下一个结点。然后我们定义了一个`insert`函数，用于向链表中插入新的结点。我们还定义了一个`print`函数，用于打印链表中的所有结点。

在主函数中，我们创建了一个空链表，并使用`insert`函数将五个元素插入链表中。然后我们使用`bubble_sort`函数对链表进行排序，并使用`print`函数打印排序后的链表。

在`bubble_sort`函数中，我们使用了一个`swapped`变量来标记是否进行了交换操作。我们使用两个指针`p`和`q`，分别指向链表中的相邻结点和当前最后一个结点。在每次循环中，我们比较`p`和`p->next`中的数据，如果前者大于后者，则进行交换操作，并将`swapped`置为`1`。最后，我们将`q`指向`p`，表示当前最后一个结点为`p`。如果在一次循环中没有进行任何交换操作，则说明链表已经有序，可以退出循环。