试以单链表为存储结构，实现简单的选择排序算法

单链表选择排序的基本思路是：在未排序的序列中找到最小元素，将其放到已排序序列的末尾。具体实现过程如下：

1. 定义单链表结构体和节点结构体

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

struct LinkedList {
    ListNode* head;
    LinkedList() : head(NULL) {}
};

2. 实现选择排序函数

void selectionSort(LinkedList& list) {
    ListNode* p = list.head;
    while (p != NULL) {
        ListNode* minNode = p;
        ListNode* q = p->next;
        while (q != NULL) {
            if (q->val < minNode->val) {
                minNode = q;
            }
            q = q->next;
        }
        // 将最小值节点交换到已排序序列的末尾
        int temp = p->val;
        p->val = minNode->val;
        minNode->val = temp;
        p = p->next;
    }
}

3. 测试

int main() {
    LinkedList list;
    list.head = new ListNode(3);
    list.head->next = new ListNode(1);
    list.head->next->next = new ListNode(4);
    list.head->next->next->next = new ListNode(2);
    selectionSort(list);
    ListNode* p = list.head;
    while (p != NULL) {
        cout << p->val << " ";
        p = p->next;
    }
    return 0;
}

输出结果为：1 2 3 4