17370845950

标准C++单链表节点定义为struct ListNode含int val和ListNode* next，构造函数须初始化next为nullptr；头插O(1)，尾插O(n)，按索引插入需校验index∈[0,size]；删除须防内存泄漏；查改操作应复用指针定位逻辑。

怎么定义一个标准的 C++ 单链表节点

单链表节点的核心是「数据 + 指向下一个节点的指针」，C++ 中必须用 struct 或 class 封装，不能只写裸指针。常见错误是忘记初始化 next，导致野指针访问崩溃。

• next 成员必须显式初始化为 nullptr（C++11 起），避免悬空指针
• 建议用 struct（默认 public）更简洁；若需封装逻辑，再改用 class
• 不要在节点里存「前驱指针」——那是双向链表的事，加了反而混淆单链表语义

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

头插、尾插、按索引插入怎么写才安全

插入操作最容易出错的是空链表处理和边界越界。头插最简单（时间 O(1)），尾插需遍历（O(n)），按索引插入必须校验 index 是否在 [0, size] 范围内（注意：允许在末尾插入，即 index == size 是合法的）。

• 头插：新建节点 → newNode->next = head → head = newNode
• 尾插：先判空，再用 while (cur->next) 找到最后节点，cur->next = newNode
• 按索引插入：用 for (int i = 0; i 移动，插入前务必检查 cur 是否为 nullptr

典型错误：insert(5, 10) 在只有 3 个节点的链表中执行，不校验直接访问第 4 个节点 → segmentation fault。

删除节点时为什么总崩？关键检查点在哪

删除失败几乎都源于三类问题：删空链表、删不存在的索引、删头节点后没更新 head。尤其注意：删头节点不能只写 head = head->next，必须先保存原 head 再 delet

• 删头节点：先 ListNode* tmp = head，再 head = head->next，最后 delete tmp
• 删中间/尾节点：找到待删节点的前驱 prev，执行 prev->next = prev->next->next，再 delete 原节点
• 所有删除前必须检查 head == nullptr，且索引 index >= 0

漏掉 delete 是 C++ 链表最隐蔽的 bug —— 程序跑得通但内存持续增长。

查找和修改为什么不能直接返回值而要返回指针

查（get(index)）和改（update(index, val)）本质都是定位节点。返回 int 值只能读，无法支持后续修改；返回 ListNode* 才能复用查找逻辑，也符合链表「通过指针操作」的本质。

• get() 应返回 int，但内部必须先用指针遍历定位，失败时返回约定值（如 -1）并设标志位或抛异常
• update() 必须先调用类似 findNode(index) 辅助函数获取指针，再改 ptr->val = val
• 别写 if (get(i) == x) update(i, y) —— 这是两次遍历，O(2n)，应合并为一次遍历

实际工程中，findNode() 这类辅助函数不暴露给用户，只在类内复用，否则接口太碎、语义不清。