设待排序的记录序列用单链表作存储结构，编写直接插入排序或简单选择排序的程序

答案：

对于直接插入排序来说，我们可以从第二个节点开始遍历整个单链表，依次将每个节点插入到有序的位置上，直到所有的节点都被插入完毕。

代码如下：

void insertSort(Node* head) {
    if (!head) return;

    Node *p = head->next;  // 从第二个节点开始
    while (p) {
        Node *prev = head;
        Node *q = head->next;
        while (q != p && q->data <= p->data) {
            prev = q;
            q = q->next;
        }

        if (q != p) {  // 说明 p 需要插入到 prev 和 q 中间
            prev->next = p;
            Node *tmp = p->next;
            p->next = q;
            p = tmp;
        } else {
            p = p->next;  // p 在有序序列中，继续往后遍历
        }
    }
}

对于简单选择排序来说，我们可以从第一个节点开始遍历整个单链表，每次选择最小的节点放到有序的位置上。

代码如下：

void selectSort(Node* head) {
    if (!head) return;

    Node *p = head->next;  // 从第一个节点开始
    while (p->next) {
        Node *minPrev = p;
        Node *q = p->next;
        while (q) {
            if (q->data < minPrev->data) {  // 找到更小的节点
                minPrev = q;
            }
            q = q->next;
        }

        if (minPrev != p) {  // 说明找到了更小的节点，需要交换
            int tmp = p->data;
            p->data = minPrev->data;
            minPrev->data = tmp;
        }
        p = p->next;  // 继续往后遍历
    }
}