c++写一个复制单链表的算法，将已知单链表中的每个结点进行复制为一个新结点，并插入到新的单链表中，要求算法的时间复杂度为O(n)。

在 C++ 中，复制单链表通常涉及到遍历原链表并在遍历时创建新的节点。这里是一个简单的 O(n) 时间复杂度的算法实现：

#include <iostream>
using namespace std;

// 定义链表节点结构体
struct ListNode {
    int val; // 节点值
    ListNode* next; // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {} // 构造函数
};

// 复制链表函数
ListNode* copyList(ListNode* head) {
    if (head == NULL) return NULL; // 如果链表为空，则直接返回空

    ListNode* dummy = new ListNode(0); // 创建一个虚拟头节点
    ListNode* tail = dummy; // 尾部指向当前正在处理的节点

    while (head != NULL) {
        ListNode* newNode = new ListNode(head->val); // 创建新节点并保存值
        tail->next = newNode; // 新节点连接到尾部之后
        tail = newNode; // 更新尾部指针
        head = head->next; // 移动原链表头部
    }

    return dummy->next; // 返回新链表的头部
}

int main() {
    // 测试示例
    ListNode* origin = new ListNode(1);
    origin->next = new ListNode(2);
    origin->next->next = new ListNode(3);

    ListNode* copiedList = copyList(origin);
    while (copiedList != NULL) {
        cout << copiedList->val << " ";
        copiedList = copiedList->next;
    }
    cout << endl;

    delete origin; // 别忘了释放原始链表内存
    return 0;
}

这个算法首先检查链表是否为空，然后逐个复制节点，并将它们添加到新链表中。因为需要遍历整个链表一次，所以时间复杂度为 O(n)，其中 n 是原链表的长度。