考研笔记

板子：删除值为 x 的结点

删除结点需要知道它的前驱，所以用 pre、p 两个指针一起走：删掉 p 时 pre 不动；没删时两个一起后移。

代码

void delX(LinkList L, int x) {              // 删除所有值为 x 的结点
    LNode *pre = L, *p = L->next;           // pre 始终是 p 的前驱
    while (p != NULL) {
        if (p->data == x) {
            pre->next = p->next;            // 摘掉 p
            free(p);
            p = pre->next;                  // pre 不动，p 指向下一个待检查的结点
        } else {
            pre = p;                        // 没删：两个一起后移
            p = p->next;
        }
    }
}
 
void dedupList(LinkList L) {                // 有序链表去重：值相同的只留第一个
    LNode *p = L->next;
    if (p == NULL) return;                  // 空表
    while (p->next != NULL) {               // p 的后继存在，才有东西可比
        LNode *q = p->next;
        if (q->data == p->data) {           // 后继和 p 相同：删掉后继，p 不动
            p->next = q->next;
            free(q);
        } else p = q;                       // 不同：p 后移
    }
}

复杂度：时间 ，空间 。

变形

  • 删除值在 之间的结点：把 p->data == x 换成 p->data >= s && p->data <= t。
  • 删除最小值结点：要删哪个结点得扫完才知道，所以扫的时候同时记下当前最小的结点 minp 和它的前驱 minpre，扫完再删。
  • 无序链表去重：值域小时用辅助数组标记，见 链表按绝对值去重；否则只能对每个结点往后扫一遍，。

易错点

  • 删除后 pre 不能后移：新的 p 还没检查过，pre 仍然是它的前驱。
  • free(p) 之后不能再访问 p->next，所以要先 pre->next = p->next，再 free。
  • 顺序表里对应的是 k 计数法，见 删除所有值为 x 的元素。

链接

反向链接