建立两个单链表。 2、编写单链表直接插入的排序算法。 3、编写单链表直接选择的排序算法。 对本实验内容设计的C++类定义，设计算法完成每个成员函数。 2.将算法转化为C++程序，设计主函数完成对每个成员函数的调用

1. 建立两个单链表：

可以通过以下步骤来建立两个单链表：

1）定义单链表结构体，包括数据域和指针域；
2）初始化头节点；
3）循环读入数据，每次新建一个节点并将数据存入节点的数据域中，将该节点插入到链表尾部；
4）重复以上步骤，建立第二个单链表。

具体代码实现如下：

#include<iostream>
using namespace std;

//定义单链表结构体
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

//建立单链表函数
ListNode* buildList() {
    ListNode* head = new ListNode(-1); //初始化头节点
    ListNode* p = head;
    int n, x;
    cout << "请输入链表长度：";
    cin >> n;
    for (int i = 0; i < n; i++) {
        cout << "请输入第" << i + 1 << "个节点的值：";
        cin >> x;
        ListNode* node = new ListNode(x);
        p->next = node;
        p = node;
    }
    return head->next;
}

int main() {
    cout << "建立第一个单链表：" << endl;
    ListNode* l1 = buildList();
    cout << "建立第二个单链表：" << endl;
    ListNode* l2 = buildList();
    return 0;
}

2. 单链表直接插入的排序算法：

直接插入排序的思路是从无序序列中取出一个元素插入到有序序列中，使得插入后的序列依然有序。具体操作是将待插入元素与有序序列中的元素从后向前依次比较，找到合适的位置进行插入。

具体代码实现如下：

//单链表直接插入排序
ListNode* insertionSortList(ListNode* head) {
    if (head == NULL || head->next == NULL) return head; //链表为空或只有一个节点，直接返回
    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    ListNode* lastSorted = head; //lastSorted指向已排序部分的最后一个节点
    ListNode* cur = head->next; //cur指向待排序部分的第一个节点
    while (cur != NULL) {
        if (lastSorted->val <= cur->val) { //如果待排序节点比已排序部分最后一个节点大，直接放到最后
            lastSorted = lastSorted->next;
        }
        else { //否则在已排序部分中找到合适的位置插入
            ListNode* pre = dummy; //pre指向待插入位置的前一个节点
            while (pre->next->val <= cur->val) {
                pre = pre->next;
            }
            lastSorted->next = cur->next; //将待排序节点从原位置删除
            cur->next = pre->next; //将待排序节点插入到pre之后
            pre->next = cur;
        }
        cur = lastSorted->next; //更新cur指向下一个待排序节点
    }
    return dummy->next;
}

3. 单链表直接选择的排序算法：

直接选择排序的思路是从无序序列中找到最小元素，然后将其放到有序序列的末尾。具体操作是每次在无序序列中找到最小元素，将其与无序序列的第一个元素交换位置，使得无序序列的长度减一，有序序列的长度加一。

具体代码实现如下：

//单链表直接选择排序
ListNode* selectionSortList(ListNode* head) {
    if (head == NULL || head->next == NULL) return head; //链表为空或只有一个节点，直接返回
    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    ListNode* lastSorted = head; //lastSorted指向已排序部分的最后一个节点
    while (lastSorted->next != NULL) { //当还有未排序的节点时
        ListNode* minNode = lastSorted->next; //minNode指向未排序部分中最小节点
        ListNode* preMinNode = lastSorted; //preMinNode指向minNode前一个节点
        ListNode* cur = minNode->next; //cur指向未排序部分中的第二个节点
        while (cur != NULL) { //找到未排序部分中最小节点及其前驱节点
            if (cur->val < minNode->val) {
                minNode = cur;
                preMinNode = lastSorted;
            }
            cur = cur->next;
        }
        //将minNode从原位置删除并插入到已排序部分末尾
        preMinNode->next = minNode->next;
        minNode->next = lastSorted->next;
        lastSorted->next = minNode;
        lastSorted = lastSorted->next; //更新lastSorted指向已排序部分的最后一个节点
    }
    return dummy->next;
}

完整代码如下：

#include<iostream>
using namespace std;

//定义单链表结构体
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

//建立单链表函数
ListNode* buildList() {
    ListNode* head = new ListNode(-1); //初始化头节点
    ListNode* p = head;
    int n, x;
    cout << "请输入链表长度：";
    cin >> n;
    for (int i = 0; i < n; i++) {
        cout << "请输入第" << i + 1 << "个节点的值：";
        cin >> x;
        ListNode* node = new ListNode(x);
        p->next = node;
        p = node;
    }
    return head->next;
}

//单链表直接插入排序
ListNode* insertionSortList(ListNode* head) {
    if (head == NULL || head->next == NULL) return head; //链表为空或只有一个节点，直接返回
    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    ListNode* lastSorted = head; //lastSorted指向已排序部分的最后一个节点
    ListNode* cur = head->next; //cur指向待排序部分的第一个节点
    while (cur != NULL) {
        if (lastSorted->val <= cur->val) { //如果待排序节点比已排序部分最后一个节点大，直接放到最后
            lastSorted = lastSorted->next;
        }
        else { //否则在已排序部分中找到合适的位置插入
            ListNode* pre = dummy; //pre指向待插入位置的前一个节点
            while (pre->next->val <= cur->val) {
                pre = pre->next;
            }
            lastSorted->next = cur->next; //将待排序节点从原位置删除
            cur->next = pre->next; //将待排序节点插入到pre之后
            pre->next = cur;
        }
        cur = lastSorted->next; //更新cur指向下一个待排序节点
    }
    return dummy->next;
}

//单链表直接选择排序
ListNode* selectionSortList(ListNode* head) {
    if (head == NULL || head->next == NULL) return head; //链表为空或只有一个节点，直接返回
    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    ListNode* lastSorted = head; //lastSorted指向已排序部分的最后一个节点
    while (lastSorted->next != NULL) { //当还有未排序的节点时
        ListNode* minNode = lastSorted->next; //minNode指向未排序部分中最小节点
        ListNode* preMinNode = lastSorted; //preMinNode指向minNode前一个节点
        ListNode* cur = minNode->next; //cur指向未排序部分中的第二个节点
        while (cur != NULL) { //找到未排序部分中最小节点及其前驱节点
            if (cur->val < minNode->val) {
                minNode = cur;
                preMinNode = lastSorted;
            }
            cur = cur->next;
        }
        //将minNode从原位置删除并插入到已排序部分末尾
        preMinNode->next = minNode->next;
        minNode->next = lastSorted->next;
        lastSorted->next = minNode;
        lastSorted = lastSorted->next; //更新lastSorted指向已排序部分的最后一个节点
    }
    return dummy->next;
}

int main() {
    cout << "建立第一个单链表：" << endl;
    ListNode* l1 = buildList();
    cout << "建立第二个单链表：" << endl;
    ListNode* l2 = buildList();

    cout << "对第一个单链表进行直接插入排序：" << endl;
    l1 = insertionSortList(l1);
    cout << "排序后结果为：";
    while (l1 != NULL) {
        cout << l1->val << " ";
        l1 = l1->next;
    }
    cout << endl;

    cout << "对第二个单链表进行直接选择排序：" << endl;
    l2 = selectionSortList(l2);
    cout << "排序后结果为：";
    while (l2 != NULL) {
        cout << l2->val << " ";
        l2 = l2->next;
    }
    cout << endl;

    return 0;
}