C++在有序单链表中插入x

在C++中，如果你有一个已排序的单链表，你想插入一个新值`x`，通常你会执行以下步骤：

1. **创建新节点**：首先，你需要创建一个新的链表节点，该节点的数据域存储`x`。

struct ListNode {
    int data;
    ListNode* next;
};
ListNode* newNode = new ListNode{x};

2. **处理边界条件**：检查链表是否为空。如果空，则直接将新节点设置为头节点。

if (head == nullptr) {
    head = newNode;
} else {

3. **遍历查找位置**：遍历已排序的链表，找到插入位置，使得新节点保持链表的升序。这可能涉及到比较新节点的值和当前节点的值。

while (prev != nullptr && prev->data > x) {
    prev = prev->next; // 遍历，更新prev指向前一个元素
}

4. **插入新节点**：找到合适的位置后，插入新节点。如果`prev`为nullptr，说明需要添加到列表头部；否则，将`newNode`的`next`指向前一个元素的下一个元素，并更新`prev`的`next`指向新节点。

prev->next = newNode;
if (prev == nullptr) {
    head = newNode;
} else {
    newNode->next = prev->next;
}

5. **释放旧节点（可选）**：如果`newNode`替换的是原来的头节点，你可能不需要这个步骤，因为`newNode`已经接替了它的职责。但如果它不是头节点，记得删除旧头节点。

// 如果删除旧头节点
if (prev == nullptr) {
    delete newNode;
}

完成以上操作后，你就成功地在有序单链表中插入了新的值`x`。