单向链表排序c++头歌

单向链表排序可以通过不同的排序算法来实现，比如冒泡排序、插入排序、选择排序、归并排序和快速排序等。下面以冒泡排序为例进行说明。

冒泡排序是一种简单的排序算法，它重复地遍历链表，并通过两个相邻节点的比较来交换节点的位置，直到整个链表有序为止。具体实现步骤如下：

1. 设置两个指针，一个指向链表的头节点，另一个指向头节点的下一个节点。
2. 遍历链表，比较当前节点和下一个节点的值，如果需要交换位置则交换。
3. 继续遍历链表，直到指针指向链表的尾节点。
4. 如果有任何节点交换了位置，则重新开始遍历链表，直到没有节点需要交换位置为止。
5. 链表排序完成。

下面是使用C语言实现的单向链表排序代码：

#include <stdio.h>

// 定义链表节点结构
struct ListNode {
    int val;
    struct ListNode *next;
};

// 冒泡排序函数
void bubbleSort(struct ListNode *head) {
    if (head == NULL || head->next == NULL) {
        return;
    }

    int swapped;
    struct ListNode *ptr1;
    struct ListNode *lptr = NULL;

    do {
        swapped = 0;
        ptr1 = head;

        while (ptr1->next != lptr) {
            if (ptr1->val > ptr1->next->val) {
                // 交换节点位置
                int tmp = ptr1->val;
                ptr1->val = ptr1->next->val;
                ptr1->next->val = tmp;
                swapped = 1;
            }
            ptr1 = ptr1->next;
        }
        lptr = ptr1;
    } while (swapped);
}

// 测试用例
int main() {
    // 创建链表
    struct ListNode n1, n2, n3, n4;
    n1.val = 4;
    n2.val = 2;
    n3.val = 1;
    n4.val = 3;
    n1.next = &n2;
    n2.next = &n3;
    n3.next = &n4;
    n4.next = NULL;

    // 排序链表
    bubbleSort(&n1);

    // 输出排序结果
    struct ListNode *ptr = &n1;
    while (ptr != NULL) {
        printf("%d ", ptr->val);
        ptr = ptr->next;
    }

    return 0;
}

以上代码中，我们首先定义了一个链表节点结构 `struct ListNode`，包含一个整数值 `val` 和一个指向下一个节点的指针 `next`。然后我们使用冒泡排序算法实现了 `bubbleSort` 函数，最后在 `main` 函数中创建了一个测试用例并进行排序输出。输出结果为 `1 2 3 4`，表示链表已经按照从小到大的顺序进行了排序。