如何在C++中实现带头节点的链表直接插入排序算法？

在C++中，实现带头节点的链表直接插入排序通常涉及到以下几个步骤：

1. **定义链表结构**：

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {} // 带头节点构造函数
};

2. **辅助函数**：创建一个新的链表节点和比较函数，用于找到合适的位置插入新元素。

ListNode* createNewNode(int val) {
    return new ListNode(val);
}

int compare(const ListNode* a, const ListNode* b) {
    return a->val < b->val ? -1 : a->val > b->val ? 1 : 0; // 按升序比较
}

3. **插入排序算法**：

void insertionSortList(ListNode*& head) {
    ListNode* dummy = new ListNode(0); // 创建虚拟头节点
    dummy->next = head;

    ListNode* current = dummy;
    ListNode* prev = dummy;
    
    while (current != nullptr && current->next != nullptr) {
        if (compare(current->next, current) >= 0) { // 如果下一个节点值大于等于当前节点，移动到下一位
            prev = current;
            current = current->next;
        } else { // 插入当前节点到正确位置
            ListNode* temp = current->next;
            prev->next = temp;
            
            while (temp != nullptr && compare(prev, temp) <= 0) {
                prev = temp;
                temp = temp->next;
            }
            prev->next = temp;
            current = temp;
        }
    }

    delete dummy->next; // 删除虚拟头节点
    dummy->next = nullptr;
    delete dummy;
}

这个算法首先创建一个虚拟头节点，然后遍历链表，每次将当前节点与下一个节点比较，如果下一个节点应该在当前节点之前，则继续遍历；否则就调整指针，将当前节点插入到正确的位置。