考研笔记

板子：建表（头插法、尾插法）与插入删除

链表的操作都能拆成两个基本动作：在 p 后面插入 s、删除 p 的后继。头插法、尾插法建表就是一直重复「插入」。

两个基本动作

// 速记：在 p 之后插入 s
s->next = p->next;          // ① s 先接上 p 原来的后继
p->next = s;                // ② p 再指向 s。①② 不能颠倒，否则 p 原来的后继就丢了
 
// 速记：删除 p 的后继 q
q = p->next;
p->next = q->next;          // p 直接跳过 q
free(q);

要删除一个结点，必须先拿到它的前驱，所以删除类的题都要带一个 pre 指针。

建表

LinkList headInsert(int A[], int n) {       // 头插法：链表顺序和输入顺序相反
    LinkList L = (LNode *)malloc(sizeof(LNode));
    L->next = NULL;                         // 先建一个只有头结点的空表
    for (int i = 0; i < n; i++) {
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s->data = A[i];
        s->next = L->next;                  // 每个新结点都插到头结点后面
        L->next = s;
    }
    return L;
}
 
LinkList tailInsert(int A[], int n) {       // 尾插法：链表顺序和输入顺序相同
    LinkList L = (LNode *)malloc(sizeof(LNode));
    LNode *r = L;                           // r 始终指向当前的表尾
    for (int i = 0; i < n; i++) {
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s->data = A[i];
        r->next = s;                        // 接到表尾后面
        r = s;                              // s 成为新的表尾
    }
    r->next = NULL;                         // 最后把表尾的 next 置空
    return L;
}

复杂度：两种都是时间 。

教材是一边 scanf 一边建表，读到 9999 结束。逻辑完全一样，这里改成从数组读，写起来更直观。

易错点

  • 头插法建出来的顺序和输入相反，就地逆置用的正是这一点，见 链表就地逆置。
  • 尾插法最后的 r->next = NULL 不能漏。漏了的话表尾的 next 是野指针，遍历停不下来。
  • 带头结点的好处：在第一个数据结点前插入、删除第一个数据结点，写法都和其他位置一样，不用特判。
  • malloc 返回的是 void *，C++ 里必须强转成 (LNode *)。

链接

反向链接