此页面需较新浏览器(支持 SharedArrayBuffer)。请升级 Chrome、Edge、Firefox 或 Safari 至最新版本。
用指针连起来的节点
- 链表是一串叫做节点的小结构体,散落在堆的各处。
- 每个节点存一个值,以及一个指向下一个节点的指针。顺着指针就能遍历链表。
- 和数组不同,链表可以一次加一个节点,而不用移动其他节点。
自引用的结构体
- 节点是一个包含指向自己类型指针的结构体:
struct Node { int data; struct Node *next; };——data是值,next指向后面那个节点。- 这个
Node在每个起始代码里都替你写好了。最后一个节点的next是NULL。
head 与 NULL 结尾
- 一个单独的指针 head 指向第一个节点。从它出发就能到达其余的节点。
- 最后一个节点指向
NULL,它标记链表的结尾。 - 空链表就是
head == NULL—— 一个节点都没有。
English
#include <stdio.h>
typedef struct Node { int data; struct Node *next; } Node;
int main(void) {
// A tiny list on the stack: 10 -> 20 -> 30 -> NULL
Node n3 = {30, NULL};
Node n2 = {20, &n3};
Node n1 = {10, &n2};
const Node *head = &n1;
// Walk it: follow ->next until NULL, counting nodes
int count = 0;
const Node *cur = head; // start at the head
while (cur != NULL) { // stop at the NULL end
count++;
cur = cur->next; // step to the next node
}
printf("length = %d\n", count); // length = 3
return 0;
}
在头部加一个节点
- 要在头部添加,新建一个节点,把它的
next指向旧的 head,再把这个新节点作为新的 head 返回。 - 这很快 —— 它不碰任何其他节点。
- 因为 head 变了,函数要返回新的 head,调用者把它存起来。
常见错误
- 绝不能弄丢
head指针,否则整条链表都找不到。 - 释放每个节点;最后一个节点指向
NULL。
现在轮到你
- 用一个
cur指针和cur = cur->next遍历链表,在NULL处停止。 - 新节点来自
malloc(sizeof(Node));检查器会释放整个链表。不要自己写main。
探索
节点与指针
每个节点指向下一个;通过重新连接来插入/删除。
难度 5/5 · 今日首次完成可获 400 金币及少量额外奖励
完成 int length(const Node *head),让它数出链表里有多少个节点(空链表为 0)。用 ->next 遍历直到 NULL。Node 类型已给出。不要写 main。
点击“运行”查看此处输出。
难度 5/5 · 今日首次完成可获 400 金币及少量额外奖励
完成 int sum_list(const Node *head),让它返回每个节点 data 的总和(空链表为 0)。Node 类型已给出。不要写 main。
点击“运行”查看此处输出。
难度 5/5 · 今日首次完成可获 400 金币及少量额外奖励
完成 Node *push_front(Node *head, int value),让它用 malloc 新建一个节点,把它的 next 指向旧的 head,并把它作为新的 head 返回。检查器会释放链表。不要写 main。
点击“运行”查看此处输出。