P4859 链表删除结点2（基础）

解题思路

第一步，理解题意。 先创建一个链表，按顺序存放 1、2、3、4、5 五个数字。然后输入一个数 n（保证 1 到 5 之间），把链表中存放数字 n 的那个结点删除，最后从链表的第一个结点开始，依次输出剩下的数字，数字之间用空格分隔。

第二步，认识链表。 链表是一串"手拉手"的结点，每个结点用 struct Node 定义：一个 int 类型的 num 存数字，一个 Node* 类型的 next 存下一个结点的地址。用 new 关键字动态创建 5 个结点，head 记住第一个结点，tail 记住最后一个结点，每建一个结点就挂到链表末尾，形成 1→2→3→4→5 的链表。

第三步，删除结点的两种写法。 单向链表只能从前往后走，所以删除分两种情况：

• 如果要删的是头结点：直接让 head 指向第二个结点，再用 delete 释放旧头结点。注意要先存下旧头结点，不能丢。
• 如果要删的是中间或尾巴上的结点：必须"拿着前一个结点"，让前一个结点的 next 跳过被删结点，直接指向被删结点的下一个。用一个指针 p 从头走，检查 p->next 的 num 是不是 n，是的话就删除它。

第四步，遍历输出。 删除完成后，从 head 开始，用一个指针 q 依次输出每个结点的 num，中间用空格分隔。第一个数字前不加空格，后面的数字前加空格。

第五步，边界情况。 输入 n=1 时，删的是头结点，输出 2 3 4 5；输入 n=5 时，删的是尾结点，输出 1 2 3 4。无论 n 是几，链表里保证恰好有一个数字等于 n。举个例子：输入 1，头结点就是 1，直接删除它，剩下 2 3 4 5，和样例一致。

参考代码

// 链表删除结点2：建1~5的链表，删除值为n的结点后输出
#include <iostream>
using namespace std;
struct Node {       // 链表结点
    int num;
    Node *next;
};
int main() {
    Node *head = 0, *tail = 0;
    for (int i = 1; i <= 5; i++) {   // 建链表，存1~5
        Node *p = new Node;
        p->num = i;
        p->next = 0;
        if (head == 0) head = p;
        else tail->next = p;
        tail = p;
    }
    int n;
    cin >> n;
    while (head != 0 && head->num == n) {  // 若要删的是头结点
        Node *t = head;
        head = head->next;
        delete t;
    }
    Node *p = head;
    while (p != 0 && p->next != 0) {       // 删中间或尾结点
        if (p->next->num == n) {
            Node *t = p->next;
            p->next = t->next;
            delete t;
        } else {
            p = p->next;
        }
    }
    Node *q = head;
    int first = 1;
    while (q != 0) {                       // 依次输出剩余结点
        if (!first) cout << ' ';
        cout << q->num;
        first = 0;
        q = q->next;
    }
    cout << endl;
    return 0;
}

复杂度分析

时间复杂度：链表一共 5 个结点，从前往后最多走一遍就能找到并删除目标，所以是 O(5) 的常数时间。

空间复杂度：只创建了 5 个固定结点，是 O(1) 的常数空间。