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

在C++中，要在已排序的动态单链表L中插入值为x的新节点，并保持链表有序，可以按照以下步骤编写算法：

1. 首先，创建一个新的节点new_node，其数据域设置为x。

2. 初始化两个指针current（当前节点）和prev（前一个节点），将它们都指向链表的头结点head。

3. 使用while循环遍历链表，直到找到合适的位置插入新节点：
a. 如果current的下一个节点的数据大于x，说明应该在这个位置之前插入，所以将new_node链接到current之后，然后更新prev和current为current和current.next。
b. 如果current的下一个节点的数据小于等于x，表示找到了合适的位置，只需将new_node链接到current.next之前，并停止循环。这时，prev.next = new_node; current.next = new_node.next;

4. 当遍历结束时，如果链表为空或第一个元素就是x，那么直接将new_node设为head（因为不需要插入）。

以下是这个算法的伪代码：

Node* insertSortedList(Node* head, int x) {
    Node* new_node = new Node(x); // 创建新节点
    Node* current = head;
    Node* prev = head;

    while (current && current->next && current->next->data <= x) {
        prev = current;
        current = current->next;
    }

    if (!current || current->data == x) {
        new_node->next = head;
        if (head)
            head->prev = new_node;
        else
            new_head = new_node;
    } else {
        prev->next = new_node;
        new_node->prev = prev;
        new_node->next = current;
    }

    return head;
}