给定一个带头节点的单链表设计算法，按递增次序输出单列表中各节点的数据元素，并释放节点所占的存储空间，要求不使用数组作为辅助空间。用C++写出代码

要按递增次序输出单链表中各节点的数据元素，并释放节点所占的存储空间，可以使用归并排序的思想。归并排序是一种有效的排序算法，其时间复杂度为O(n log n)，并且可以在原地进行排序，不需要额外的数组作为辅助空间。

下面是使用C++实现的代码：

#include <iostream>
using namespace std;

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

// 合并两个有序链表
ListNode* merge(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    while (l1 && l2) {
        if (l1->val < l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    tail->next = l1 ? l1 : l2;
    return dummy.next;
}

// 分割链表
void split(ListNode* head, ListNode** front, ListNode** back) {
    ListNode* slow = head;
    ListNode* fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    *front = head;
    *back = slow->next;
    slow->next = nullptr;
}

// 归并排序
ListNode* mergeSort(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode* front = nullptr;
    ListNode* back = nullptr;
    split(head, &front, &back);
    front = mergeSort(front);
    back = mergeSort(back);
    return merge(front, back);
}

// 打印链表并释放内存
void printAndFreeList(ListNode* head) {
    while (head) {
        cout << head->val << " ";
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
    cout << endl;
}

int main() {
    // 创建带头节点的单链表
    ListNode* head = new ListNode(0); // 头节点不存储有效数据
    ListNode* current = head;
    int values[] = {4, 2, 5, 3, 1}; // 示例数据
    for (int value : values) {
        current->next = new ListNode(value);
        current = current->next;
    }

    // 对链表进行归并排序
    head->next = mergeSort(head->next);

    // 打印排序后的链表并释放内存
    printAndFreeList(head->next);

    // 释放头节点
    delete head;

    return 0;
}

### 代码说明：
1. **ListNode结构体**：定义了单链表节点的结构体。
2. **merge函数**：合并两个有序链表。
3. **split函数**：将链表分成两半。
4. **mergeSort函数**：递归地对链表进行归并排序。
5. **printAndFreeList函数**：打印链表并释放每个节点的内存。
6. **main函数**：创建一个带头节点的单链表，插入一些示例数据，然后对其进行排序、打印并释放内存。

这个实现方法没有使用额外的数组作为辅助空间，完全在链表上进行操作，符合题目要求。