线性表是数据结构的入门章。顺序表靠数组，链表靠指针。下面用 带头结点的单链表 把初始化、按位插入、遍历和有序合并写清楚，并修正早期笔记里「函数名叫 Delete 实际在打印」这类命名问题。

结点定义与初始化

#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;

typedef int ElemType;
typedef struct LNode {
    ElemType data;
    LNode* next;
} LNode, *LinkList;

// 带头结点空表
bool InitList(LinkList& L) {
    L = (LinkList)malloc(sizeof(LNode));
    if (!L) return false;
    L->next = nullptr;
    return true;
}

头结点不存业务数据，统一插入/删除边界，是教材里最省事的写法。

按位插入（在第 i 个位置前插）

位序从 1 开始：

bool ListInsert(LinkList& L, int i, ElemType e) {
    if (i < 1) return false;
    LNode* p = L;
    int j = 0;
    while (p && j < i - 1) {
        p = p->next;
        ++j;
    }
    if (!p) return false; // i 过大

    LNode* s = (LNode*)malloc(sizeof(LNode));
    if (!s) return false;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

复杂度 (O(n))，瓶颈在查找第 (i-1) 个结点。

遍历打印

void PrintList(LinkList L) {
    for (LNode* p = L->next; p; p = p->next) {
        cout << p->data << ' ';
    }
    cout << '\n';
}

有序表合并（假设升序）

void MergeList(LinkList& La, LinkList& Lb, LinkList& Lc) {
    LNode* pa = La->next;
    LNode* pb = Lb->next;
    Lc = La;                 // 复用 La 的头结点
    LNode* pc = Lc;

    while (pa && pb) {
        if (pa->data <= pb->data) {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        } else {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
    }
    pc->next = pa ? pa : pb;
    free(Lb); // 释放 Lb 头结点；结点已链入 Lc
    Lb = nullptr;
}

时间 (O(len(a)+len(b)))，空间 (O(1)) 额外指针。

主函数演示

int main() {
    LinkList La, Lb, Lc;
    InitList(La);
    InitList(Lb);
    ListInsert(La, 1, 2);
    ListInsert(La, 2, 3);
    ListInsert(La, 3, 5);
    PrintList(La); // 2 3 5
    return 0;
}

旧笔记问题对照

旧代码 问题 修正
Delete_L 实际在打印 改名 PrintList
缺少空指针检查 malloc 失败未处理 返回 bool
合并后 Lb 悬空 头结点 free 后未置空 Lb = nullptr
无销毁函数 长期运行泄漏 应补 DestroyList

何时用链表 vs 顺序表

操作 顺序表 链表
随机访问 (O(1)) (O(n))
任意位置插入删除 (O(n)) 搬移 (O(1)) 改指针（已知位置）
缓存友好 好 差

笔试面试里，带头结点单链表几乎是必默写项；真正工程中更常用 std::vector / std::list，但指针基本功仍要过关。

小结

线性表链表实现的核心是 找准前驱指针再改 next。把插入与合并的边界条件画在纸上走一遍，比只背代码牢靠得多。