怎么写一个链表c++

要创建一个C++链表，你可以从定义节点结构开始，然后创建链表节点、插入节点以及可能的操作如查找和删除。这里我们基于引用[1]给出的示例来构建一个简单的单向链表：

// 定义链表节点
template <typename T>
struct ListNode {
    T data;
    ListNode* next;
    ListNode(T val): data(val), next(nullptr) {} // 构造函数
};

// 基本链表操作 - 插入节点
template <typename T>
void insertNode(ListNode<T>& head, const T& val) {
    ListNode<T> newNode(val);
    if (head == nullptr) {
        head = &newNode; // 如果链表为空，直接指向新节点
    } else {
        ListNode<T>* current = head;
        while (current->next != nullptr) {
            current = current->next;
        }
        current->next = &newNode; // 在最后一个节点之后插入
    }
}

// 示例：创建并插入元素到链表
int main() {
    ListNode<int> list;
    insertNode(list, 1); // 创建第一个节点，值为1
    insertNode(list, 2); // 插入第二个节点，值为2
    // 更多节点可以按此方式添加...
    return 0;
}

对于链接两个链表的问题[^2]，思路是遍历其中一个链表并反向插入到另一个链表中，这样可以保持时间复杂度为O(m + n)，其中m和n分别是两个链表的长度。具体实现如下：

ListNode<int>* reverseMerge(ListNode<int>* ha, ListNode<int>* hb) {
    if (ha == nullptr) return hb;
    ListNode<int>* tailHb = reverseMerge(ha->next, hb);
    ha->next->next = tailHb; // 逆序后的hb链表最后的节点接到ha链表尾部
    ha->next = nullptr; // 更新ha链表的下一个节点
    return ha;
}

// 使用上述函数连接两个链表
ListNode<int>* mergedList = reverseMerge(ha, hb);