第 8 课:linked list 删除节点
非 UNSW 官方材料。本文基于官方 Lecture 13/14 的 linked list 删除节点内容做中文转述;不复刻考试题,代码模板为本站原创。[S018][S019]
今天只做:画出删 head 和删 middle 的箭头变化。 下一步:主控台 · 上一课 · 下一课:linked list 综合查错 别乱跳:删除题先保
prev和curr,再考虑free。
本课目标
删除节点不要分裂成一堆补丁;先统一想成“找到前一个节点,让它跳过要删的节点”。[S018][S019]
| 情况 | 先做什么 |
|---|---|
| 空链表 | 直接返回 head |
| 删头 | 新 head 是旧 head 的 next |
| 删中间 | prev->next = curr->next |
| 删尾 | 同样是让 prev 指向 NULL |
删除第一个匹配值
Lecture 13/14 的删除主题覆盖 head、tail、middle 和单节点;下面模板把这些情况放进同一条逻辑里。[S018][S019]
struct node *delete_first(struct node *head, int value) {
struct node *curr = head;
struct node *prev = NULL;
while (curr != NULL && curr->data != value) {
prev = curr;
curr = curr->next;
}
if (curr == NULL) {
return head;
}
if (prev == NULL) {
head = curr->next;
} else {
prev->next = curr->next;
}
free(curr);
return head;
}
口诀
链表删除题先问 3 个问题:要删的是不是 NULL,要删的是不是 head,删完有没有把节点 free。[S018][S019]
5 分钟练习
- 画删除 head 的前后箭头。
- 画删除 middle 的前后箭头。
- 解释为什么
free(curr)要在改好链接之后。
本课过关标准
- 我知道空链表直接返回。
- 我知道删头会改变
head。 - 我知道删中间要保留
prev。 - 我知道找不到目标时不应该乱 free。
引用
- [S018] Lecture 13 PDF: https://cgi.cse.unsw.edu.au/~cs1511/26T1/slides/week_8/COMP1511_26T1_Lecture13.pdf
- [S019] Lecture 13/14 PDF: https://cgi.cse.unsw.edu.au/~cs1511/26T1/slides/week_9/COMP1511_26T1_Lecture1314.pdf