AB12-在带头结点的递增有序单链表中插入新结点，保持有序性¶

代码实现¶

C
/**
 * 在带头结点的递增有序单链表中插入新结点，保持有序性
 * @param L 指向链表头结点的指针
 * @param x 要插入的元素值
 */
void InsertNode(LinkList L, int x) {
    // 申请新结点空间并初始化
    LNode* p = (LNode*)malloc(sizeof(LNode));
    if (p == NULL) {
        printf("内存分配失败\n");
        return;
    }
    p->data = x;
    p->next = NULL;

    // 查找插入位置：r指向插入位置的前驱结点
    LNode* r = L;  // 从头结点开始查找

    // 遍历链表，找到第一个大于x的结点的前驱位置
    while (r->next != NULL) {
        // 如果下一个结点的值大于x，则找到插入位置
        if (r->next->data > x) {
            break;  // 找到插入位置，跳出循环
        }
        r = r->next;  // 继续向后查找
    }

    // 在r指向的位置后插入新结点p
    p->next = r->next;  // 新结点指向原r的后继
    r->next = p;        // r指向新结点
}

算法执行流程图解¶

查找插入位置过程：¶

Text Only

有序链表：L→[ ]→[1]→[3]→[7]→[9]→NULL  插入x=5

查找过程：
r=L: r->next=[1], 1>5? 否 → r=[1]
r=[1]: r->next=[3], 3>5? 否 → r=[3]  
r=[3]: r->next=[7], 7>5? 是 → 找到插入位置，跳出

插入位置：r指向[3]，在[3]和[7]之间插入5

插入操作过程：¶

Text Only

插入前：L→[ ]→[1]→[3]→[7]→[9]→NULL
               ↑     ↑
               r   r->next

插入操作：
1. p->next = r->next;  → p→[5]→[7]→[9]→NULL
2. r->next = p;        → [3]→[5]→[7]→[9]→NULL

插入后：L→[ ]→[1]→[3]→[5]→[7]→[9]→NULL

完整执行示例¶

Text Only

原链表：L→[ ]→[2]→[4]→[6]→[8]→NULL

插入x=1：
查找：r=L, r->next=[2], 2>1 → 找到位置
插入：L→[ ]→[1]→[2]→[4]→[6]→[8]→NULL

插入x=5：
查找：r=L→[2]→[4], r->next=[6], 6>5 → 找到位置
插入：L→[ ]→[1]→[2]→[4]→[5]→[6]→[8]→NULL

插入x=10：
查找：r=L→[1]→[2]→[4]→[5]→[6]→[8], r->next=NULL
插入：L→[ ]→[1]→[2]→[4]→[5]→[6]→[8]→[10]→NULL

复杂度分析¶

时间复杂度：O(n)¶

最好情况：O(1) - 插入到链表开头
最坏情况：O(n) - 插入到链表末尾
平均情况：O(n) - 平均需要查找n/2个结点
总体时间复杂度：O(n)

空间复杂度：O(1)¶

额外空间：只使用了常数个指针变量：p、r
结点空间：虽然创建了一个新结点，但这属于问题本身要求
算法额外空间复杂度：O(1)

进阶-递归版本实现¶

C
/**
 * 递归版本：在有序链表中插入元素
 */
void InsertNode_Recursive(LinkList L, int x) {
    if (L == NULL) return;

    // 创建新结点
    LinkList p = (LinkList)malloc(sizeof(LNode));
    if (p == NULL) return;
    p->data = x;

    // 递归查找插入位置
    LinkList pos = findInsertPos(L, x);
    p->next = pos->next;
    pos->next = p;
}

// 辅助函数：查找插入位置
LinkList findInsertPos(LinkList head, int x) {
    if (head->next == NULL || head->next->data > x) {
        return head;
    }
    return findInsertPos(head->next, x);
}

算法特点¶

核心思想：利用链表的有序性，找到第一个大于待插入元素值的结点的前驱位置，然后执行标准的插入操作。

关键步骤： 1. 创建结点：分配新结点空间并设置数据 2. 查找位置：遍历链表找到合适的插入位置 3. 执行插入：在指定位置插入新结点

重要性质： - 保持链表的有序性 - 插入位置唯一确定 - 时间复杂度与链表长度成正比

与顺序表插入的对比：

特性	顺序表	链表
查找时间	O(n)	O(n)
插入时间	O(n)	O(1)
总体时间	O(n)	O(n)
空间复杂度	O(1)	O(1)

链表的优势在于插入操作本身是O(1)的，但查找插入位置仍需O(n)时间。