基于链表的简单选择排序

链表的简单选择排序实现起来相对简单，具体步骤如下：

1. 定义一个指向链表头结点的指针p，初始值为链表头结点。
2. 定义一个指向链表节点的指针minp，初始值为p。
3. 从p开始遍历整个链表，找到链表中最小的节点，将其指针赋给minp。
4. 将minp指向的节点与p指向的节点进行交换。
5. 将p指针指向下一个节点。
6. 重复步骤2~5，直到链表中的所有节点都被遍历完毕。

以下是基于链表的简单选择排序的实现代码：

#include <iostream>
using namespace std;

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

void selectionSort(ListNode* head) {
    ListNode* p = head;
    while (p != NULL) {
        ListNode* minp = p;
        ListNode* q = p->next;
        while (q != NULL) {
            if (q->val < minp->val)
                minp = q;
            q = q->next;
        }
        swap(p->val, minp->val);
        p = p->next;
    }
}

int main() {
    // 构造测试链表
    ListNode* head = new ListNode(3);
    head->next = new ListNode(1);
    head->next->next = new ListNode(4);
    head->next->next->next = new ListNode(2);

    // 遍历测试链表
    cout << "Before sorting: ";
    ListNode* p = head;
    while (p != NULL) {
        cout << p->val << " ";
        p = p->next;
    }
    cout << endl;

    // 对测试链表进行简单选择排序
    selectionSort(head);

    // 遍历排序后的链表
    cout << "After sorting: ";
    p = head;
    while (p != NULL) {
        cout << p->val << " ";
        p = p->next;
    }
    cout << endl;

    // 释放链表内存
    while (head != NULL) {
        ListNode* p = head;
        head = head->next;
        delete p;
    }

    return 0;
}

输出结果为：

Before sorting: 3 1 4 2 
After sorting: 1 2 3 4