c++已知带头结点的动态单链表 L 中的结点是按整数值递增排序的，试写一算法将值为 x 的结点插入到表 L 中，使 L 仍然有序。要求算法的时间复杂度为 O(n)，空间复杂度为 O(1)。

为了在C++中按O(n)时间复杂度和O(1)空间复杂度将值为x的节点插入到递增有序的链表中，我们需要遍历链表找到合适的位置并插入新节点。这里是一个简单的示例：

首先，假设链表的定义如下（不包括头结点）：

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

算法步骤如下：

1. 初始化两个指针 `current` 和 `prev` 分别指向链表的头结点和空指针。
2. 遍历链表直到找到满足条件的节点或到达链表尾部。

void insertSortedList(ListNode *&head, int x) {
    if (head == nullptr || head->val >= x) { // 如果链表为空或当前节点大于等于x，直接插入
        ListNode *newNode = new ListNode(x);
        newNode->next = head;
        head = newNode;
    } else { // 否则遍历查找插入位置
        ListNode *current = head;
        while (current->next != nullptr && current->next->val < x) {
            prev = current;
            current = current->next;
        }
        // 插入新节点
        newNode = new ListNode(x);
        if (prev == nullptr) {
            newNode->next = head;
            head = newNode;
        } else {
            newNode->next = current->next;
            prev->next = newNode;
        }
    }
}

这个算法通过一次遍历来找到正确的位置，并创建新的节点，所以时间复杂度是O(n)，其中n是链表的长度。空间复杂度是O(1)，因为我们只使用了常数级别的额外空间来存储临时变量。