2.2 单链表

结点结构与头结点，头插法/尾插法建表，按位查找、插入与删除，以及链表算法题的常用技巧。

为什么需要链表

顺序表插入删除要移动大量元素，并且需要一整块连续空间。链式存储不要求逻辑上相邻的元素在物理位置上也相邻，它通过”指针”建立元素之间的逻辑关系，因此插入和删除只需修改指针——代价是失去了随机存取的能力。

结点结构

单链表的每个结点除了存放元素自身的信息（数据域）外，还要存放一个指向其后继的指针（指针域）。

typedef struct LNode {       // 定义单链表结点类型
    ElemType data;           // 数据域
    struct LNode *next;      // 指针域
} LNode, *LinkList;

LNode * 和 LinkList 本质相同。习惯上用 LinkList 强调”这是一个链表”，用 LNode * 强调”这是一个结点”。

头指针与头结点

• 头指针：链表中第一个结点的存储位置，用来标识一个链表。不管带不带头结点，头指针都始终指向链表的第一个结点。
• 头结点：为了操作方便，在单链表第一个数据结点之前附设的一个结点，数据域一般不存信息。

引入头结点的两个好处：

1. 在链表第一个位置上的操作与在其他位置上的操作一致，无须特殊处理；
2. 无论链表是否为空，头指针都指向头结点的非空指针，空表与非空表的处理统一了。

动画演示

下面的动画涵盖单链表的全部基本操作。重点观察：插入时为什么必须先执行 s->next = p->next，以及头插法、尾插法建出来的链表顺序有何不同。

1bool ListInsert(LinkList &L, int i, ElemType e) {
2    LNode *p = L; int j = 0;            // p 指向头结点
3    while (p != NULL && j < i - 1) {    // 找第 i-1 个结点
4        p = p->next;
5        j++;
6    }
7    if (p == NULL) return false;        // i 不合法
8    LNode *s = (LNode*)malloc(sizeof(LNode));
9    s->data = e;
10    s->next = p->next;                  // ①
11    p->next = s;                        // ② 顺序不能颠倒
12    return true;
13}

建立单链表

头插法

每读入一个元素，就申请新结点，并把它插入到头结点之后。

• 关键两步：s->next = L->next; L->next = s;
• 读入顺序与链表中元素顺序相反——这一特性常用于链表逆置。
• 每个结点插入时间为 $O(1)$，建表总时间 $O(n)$。

尾插法

增设一个尾指针 r，使其始终指向当前链表的表尾结点，新结点直接接在 r 之后。

• 关键两步：r->next = s; r = s;，最后别忘了 r->next = NULL。
• 读入顺序与链表中元素顺序相同；时间复杂度 $O(n)$。

查找

按序号查找：从第一个结点出发，顺着指针逐个往下搜索，直到找到第 $i$ 个结点。

LNode *GetElem(LinkList L, int i) {
    if (i < 0) return NULL;
    LNode *p = L;            // p 指向头结点，视为第 0 个结点
    int j = 0;
    while (p != NULL && j < i) {
        p = p->next;
        j++;
    }
    return p;                // i = 0 返回头结点；i 过大返回 NULL
}

按序号查找与按值查找的时间复杂度都是 $O(n)$——这就是”顺序存取”的含义。

插入与删除

后插：在 p 之后插入 s

s->next = p->next;   // ①
p->next = s;         // ②

按位序插入时，先调用 GetElem(L, i-1) 找到前驱结点 p（$O(n)$），再执行上面的两步（$O(1)$），总时间 $O(n)$。

前插：在 p 之前插入 s

单链表无法直接找到 p 的前驱。一个巧妙的办法是：仍然把 s 插到 p 之后，然后交换 p 和 s 的数据域，时间复杂度 $O(1)$。

s->next = p->next;
p->next = s;
temp = p->data; p->data = s->data; s->data = temp;   // 交换数据

删除结点

删除第 $i$ 个结点：先找到第 $i-1$ 个结点 p，令 q = p->next，然后 p->next = q->next; free(q);

算法题技巧

链表题是 408 算法设计题的常客。熟练掌握以下几种”套路”可以解决大部分问题。

int SearchK(LinkList list, int k) {
    LNode *p = list->next, *q = list->next;
    int count = 0;
    while (p != NULL) {
        if (count < k) count++;   // 前 k 步只移动 p
        else q = q->next;         // 之后 p、q 同步移动
        p = p->next;
    }
    if (count < k) return 0;      // 链表长度不足 k
    printf("%d", q->data);
    return 1;
}

LinkList Reverse(LinkList L) {
    LNode *p = L->next, *r;      // p 为工作指针，r 暂存 p 的后继
    L->next = NULL;              // 先把头结点摘下
    while (p != NULL) {
        r = p->next;             // 暂存后继，防止断链
        p->next = L->next;       // 头插
        L->next = p;
        p = r;
    }
    return L;
}

即时练习