本檔收錄 6 題由易到難的練習。建議流程：先蓋住解答自己寫，卡住再看
「解題思路」，寫完對照「參考解答」。每題完整程式碼在 exercises/：
cc -std=c11 -Wall -Wextra -o /tmp/out exercises/ex1_list_queries.c && /tmp/out貫穿本單元的功夫：走訪模式 for (p = head; p; p = p->next)、
釋放模式「先存 next 再 free」、以及指標的指標消除特例。
練習 1：list_min / list_max / list_sum（難度：基礎）
題目
為單向串列加上三個查詢函式：
int list_min(const struct node *head, int *found);
int list_max(const struct node *head, int *found);
long list_sum(const struct node *head);空串列時 min/max 要能明確回報「沒有結果」（不能拿 0 或隨機值 混充），sum 對空串列回 0。所有配置的節點最後必須釋放。
解題思路
- 三個函式共用同一個走訪骨架：
for (const struct node *p = head; p != NULL; p = p->next)差別只在迴圈體做什麼（比較 vs 累加）。
2. 空串列的 min/max 是介面設計題：最小值不存在時回什麼？
- 回 0：與「真的最小值是 0」無法區分——錯誤設計；
- 回 INT_MAX：同樣可能撞到真值；
- 輸出參數 int *found：把「有沒有結果」與「結果是什麼」
分成兩個通道，呼叫端無從誤解。這是 C 沒有 optional 型別時
的標準解法。
3. sum 不需要旗標：空和 = 0 在數學上與工程上都自然。
累加器用 long 防 int 溢位（元素多時）。
4. 初始化技巧（同函式指標單元的 max_n）：min/max 用第一個
節點的值起手，從第二個節點開始比，不要用魔術常數。
5. 釋放模式：next = head->next; free(head); head = next;——
free 之後不能再讀節點，順序不能倒。
參考解答
/*
* ex1_list_queries.c — 練習 1：list_min / list_max / list_sum
*
* 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex1_list_queries.c
* 執行：/tmp/out
*
* 為單向串列加上三個查詢函式。走訪模式都一樣：
* for (p = head; p != NULL; p = p->next)
*/
#include <stdio.h>
#include <stdlib.h>
struct node {
int value;
struct node *next;
};
/* 頭插建立節點（O(1)，串列順序與插入順序相反） */
static struct node *push_front(struct node *head, int value)
{
struct node *n = malloc(sizeof *n);
if (n == NULL) {
fprintf(stderr, "out of memory\n");
exit(1);
}
n->value = value;
n->next = head;
return n;
}
/* min/max 對空串列沒有意義：用回傳值 + found 旗標處理 */
static int list_min(const struct node *head, int *found)
{
if (head == NULL) {
*found = 0;
return 0;
}
int best = head->value;
for (const struct node *p = head->next; p != NULL; p = p->next)
if (p->value < best)
best = p->value;
*found = 1;
return best;
}
static int list_max(const struct node *head, int *found)
{
if (head == NULL) {
*found = 0;
return 0;
}
int best = head->value;
for (const struct node *p = head->next; p != NULL; p = p->next)
if (p->value > best)
best = p->value;
*found = 1;
return best;
}
/* sum 對空串列自然回 0，不需旗標 */
static long list_sum(const struct node *head)
{
long sum = 0;
for (const struct node *p = head; p != NULL; p = p->next)
sum += p->value;
return sum;
}
static void print_list(const char *tag, const struct node *head)
{
printf("%s", tag);
for (const struct node *p = head; p != NULL; p = p->next)
printf(" %d", p->value);
printf("\n");
}
static void free_list(struct node *head)
{
while (head != NULL) {
struct node *next = head->next; /* 先存 next 再 free */
free(head);
head = next;
}
}
int main(void)
{
/* 頭插 7 個值：串列順序是插入順序的反轉 */
int data[] = { 42, -7, 19, 0, 88, -3, 5 };
struct node *head = NULL;
for (size_t i = 0; i < sizeof data / sizeof data[0]; i++)
head = push_front(head, data[i]);
print_list("list:", head);
int found;
int mn = list_min(head, &found);
printf("min = %d (found=%d)\n", mn, found);
int mx = list_max(head, &found);
printf("max = %d (found=%d)\n", mx, found);
printf("sum = %ld\n", list_sum(head));
/* 空串列的行為 */
int f2;
list_min(NULL, &f2);
printf("empty list: found=%d, sum=%ld\n", f2, list_sum(NULL));
free_list(head);
return 0;
}程式碼講解
- 參數型別是
const struct node *：查詢函式不改串列， 用 const 把這個承諾寫進介面，編譯器會幫忙看守。 list_min的迴圈從head->next開始——head 的值已經當初始值 用掉了，再比一次不錯但多餘。- 測資用頭插建立，所以印出順序與插入順序相反——這不影響 min/max/sum（它們與順序無關），但提醒你頭插的特性。
- 易錯處：釋放迴圈寫成
free(head); head = head->next;—— 讀取已釋放的記憶體（use-after-free），ASan 一抓一個準。
範例輸出
list: 5 -3 88 0 19 -7 42
min = -7 (found=1)
max = 88 (found=1)
sum = 144
empty list: found=0, sum=0練習 2：O(1) push_back（難度：基礎）
題目
樸素的尾插要先走到尾巴（O(n)）。實作 O(1) 版本：
維護一個含 head 與 tail 的包裝結構
struct list { struct node *head; struct node *tail; size_t len; };提供 push_back、push_front、print_list、list_free，
並示範 tail 在各操作後的位置。
解題思路
- 問題根源：單向串列只記 head，找尾巴必須走完整條。 空間換時間：多存一個 tail 指標，尾插變成三行。
- 包裝結構的價值：head/tail/len 三個欄位必須同進退，
包成一個 struct 之後，所有操作收一個
struct list *， 不變量（tail 永遠指向最後一個節點）由這組函式共同維護。 - push_back 的兩種情況：
空串列： 非空串列：
head ──> NULL head ──> [1] ──> [2]
tail ──> NULL ^tail
插入後： 插入後：
head ──> [n] head ──> [1] ──> [2] ──> [n]
tail ──> [n] ^tail空串列時 head 也要指向新節點；非空時接在 tail->next。
4. push_front 也要顧 tail：對空串列頭插，tail 同樣要設——
忘記這條是最常見的 bug（之後第一次 push_back 會接到 NULL 上）。
5. 釋放後歸零：list_free 最後把三個欄位重設，
防止呼叫端拿懸空的 head/tail 繼續用。
參考解答
/*
* ex2_push_back_o1.c — 練習 2：O(1) 的 push_back（head + tail 包裝結構）
*
* 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex2_push_back_o1.c
* 執行：/tmp/out
*
* 樸素的 push_back 要先走到尾巴：O(n)。
* 解法：把串列包進 struct list { head, tail, len }，
* tail 永遠指向最後一個節點，尾插變 O(1)。
*/
#include <stdio.h>
#include <stdlib.h>
struct node {
int value;
struct node *next;
};
/* 包裝結構：多存一個 tail 指標（與長度，順便） */
struct list {
struct node *head;
struct node *tail;
size_t len;
};
static void list_init(struct list *l)
{
l->head = NULL;
l->tail = NULL;
l->len = 0;
}
/*
* O(1) 尾插。兩種情況：
* 空串列：head 與 tail 都指向新節點
* 非空 ：接在 tail 後面，tail 前進
*/
static void push_back(struct list *l, int value)
{
struct node *n = malloc(sizeof *n);
if (n == NULL) {
fprintf(stderr, "out of memory\n");
exit(1);
}
n->value = value;
n->next = NULL; /* 新節點永遠是最後一個 */
if (l->tail == NULL) /* 空串列 */
l->head = n;
else
l->tail->next = n;
l->tail = n;
l->len++;
}
/* 對照組：O(1) 頭插 */
static void push_front(struct list *l, int value)
{
struct node *n = malloc(sizeof *n);
if (n == NULL) {
fprintf(stderr, "out of memory\n");
exit(1);
}
n->value = value;
n->next = l->head;
l->head = n;
if (l->tail == NULL) /* 原本是空串列：tail 也要設 */
l->tail = n;
l->len++;
}
static void print_list(const char *tag, const struct list *l)
{
printf("%s (len=%zu):", tag, l->len);
for (const struct node *p = l->head; p != NULL; p = p->next)
printf(" %d", p->value);
if (l->tail != NULL)
printf(" [tail=%d]", l->tail->value);
printf("\n");
}
static void list_free(struct list *l)
{
struct node *p = l->head;
while (p != NULL) {
struct node *next = p->next;
free(p);
p = next;
}
list_init(l); /* 歸零，防懸空指標 */
}
int main(void)
{
struct list l;
list_init(&l);
printf("push_back 1..5 (order preserved, each O(1)):\n");
for (int i = 1; i <= 5; i++)
push_back(&l, i);
print_list(" list", &l);
printf("\npush_front 0:\n");
push_front(&l, 0);
print_list(" list", &l);
printf("\npush_back 99 (tail moves):\n");
push_back(&l, 99);
print_list(" list", &l);
list_free(&l);
print_list("\nafter free", &l);
return 0;
}程式碼講解
n->next = NULL先設好：不管接到哪，新節點都是最後一個。- 分支只有一個：「空或非空」。兩種情況最後都做
l->tail = n; l->len++;，共同動作提出到分支外——重複程式碼是 bug 的溫床。 print_list順便印出[tail=..]，每個操作後都能目視驗證 不變量（tail 是最後一個元素）成立。- 易錯處：push_front 忘記「空串列時設 tail」；或 push_back
忘記更新
l->tail（下次插入會接錯位置，串列斷裂）。
範例輸出
push_back 1..5 (order preserved, each O(1)):
list (len=5): 1 2 3 4 5 [tail=5]
push_front 0:
list (len=6): 0 1 2 3 4 5 [tail=5]
push_back 99 (tail moves):
list (len=7): 0 1 2 3 4 5 99 [tail=99]
after free (len=0):練習 3：有序插入與插入排序（難度：進階）
題目
實作 insert_sorted，把新值插入正確位置、維持串列遞增；
用它對亂序測資 42 -7 19 0 88 -3 19 5 做插入排序，
每插入一個值就印出目前串列。要求用「指標的指標」寫法，
頭插與中間插不得有特例分支。重複值要能處理。
解題思路
- 樸素寫法的問題：用
prev/cur兩個指標找插入點， 插在頭部時prev是 NULL，要寫if (prev == NULL) head = n; else prev->next = n;的特例——兩條路徑、雙倍測試。 - 指標的指標：觀察「插入」實際改的是什麼——
要嘛改
head變數、要嘛改某個節點的next欄位。 兩者都是「一個struct node *大小的格子」！ 讓pp指向這個格子，兩種情況就統一了：
插入 5 到 -7 -3 19 42：
pp 一路指向「格子」而非節點：
pp = &head → *pp 是 -7，-7 < 5，前進
pp = &(-7)->next → *pp 是 -3，-3 < 5，前進
pp = &(-3)->next → *pp 是 19，19 >= 5，停！
接線：n->next = *pp（19 那截）；*pp = n（-3 的 next 指向 5）
-7 ──> -3 ──> [5] ──> 19 ──> 42- 迴圈條件：
*pp != NULL && (*pp)->value < value—— 走到底（插尾）或找到第一個 ≥ value 的節點（插它前面）。 用<使重複值插在既有值後面（穩定）。 - 插入排序：對每個輸入值呼叫一次 insert_sorted， 每步之後串列都有序——輸出的過程軌跡就是證明。 複雜度 O(n²)（每次插入 O(n)），與陣列版插入排序相同。
- Linus Torvalds 在 TED 訪談舉的 "good taste" 例子 正是這個模式：用間接層消除特例。
參考解答
/*
* ex3_insert_sorted.c — 練習 3：有序插入與串列插入排序
*
* 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex3_insert_sorted.c
* 執行：/tmp/out
*
* insert_sorted：把節點插入正確位置、維持串列遞增。
* 用「指標的指標」寫法：頭插與中間插共用同一段程式碼，沒有特例。
* 插入排序 = 把亂序資料逐一 insert_sorted 進新串列。
*/
#include <stdio.h>
#include <stdlib.h>
struct node {
int value;
struct node *next;
};
static struct node *new_node(int value)
{
struct node *n = malloc(sizeof *n);
if (n == NULL) {
fprintf(stderr, "out of memory\n");
exit(1);
}
n->value = value;
n->next = NULL;
return n;
}
/*
* 有序插入（遞增）。
* pp 一路指著「待檢查的 next 欄位」：
* 一開始指向 head 指標本身，之後指向前一節點的 next。
* 找到第一個 >= value 的節點就插在它前面。
* 頭插（串列空或 value 最小）與中間插走的是同一條路——
* 這就是 Linus 說的 "good taste"：用間接層消除特例。
*/
static void insert_sorted(struct node **pp, int value)
{
struct node *n = new_node(value);
while (*pp != NULL && (*pp)->value < value)
pp = &(*pp)->next; /* 前進：改指向下一個 next 欄位 */
n->next = *pp; /* 新節點接上「剩下的串列」 */
*pp = n; /* 前一個 next（或 head）指向新節點 */
}
static void print_list(const char *tag, const struct node *head)
{
printf("%s", tag);
for (const struct node *p = head; p != NULL; p = p->next)
printf(" %d", p->value);
printf("\n");
}
static void free_list(struct node *head)
{
while (head != NULL) {
struct node *next = head->next;
free(head);
head = next;
}
}
int main(void)
{
int data[] = { 42, -7, 19, 0, 88, -3, 19, 5 };
size_t n = sizeof data / sizeof data[0];
printf("insertion sort by repeated insert_sorted:\n\n");
printf("input:");
for (size_t i = 0; i < n; i++)
printf(" %d", data[i]);
printf("\n\n");
/* 插入排序：逐一插入，每步之後串列都保持有序 */
struct node *sorted = NULL;
for (size_t i = 0; i < n; i++) {
insert_sorted(&sorted, data[i]);
printf("after insert %3d:", data[i]);
print_list("", sorted);
}
print_list("\nsorted:", sorted);
/* 邊界：插進頭、插進尾 */
insert_sorted(&sorted, -100);
insert_sorted(&sorted, 999);
print_list("after -100, 999:", sorted);
free_list(sorted);
return 0;
}程式碼講解
pp = &(*pp)->next：這行是全題精華。*pp是目前節點，&(*pp)->next是它 next 欄位的位址——pp 永遠指向 「下一步可能要改寫的格子」。- 接線兩行的順序不能倒：先
n->next = *pp保住後半段， 再*pp = n接上前半段。倒過來後半段就丟了。 - 呼叫端傳
&sorted（head 指標的位址），讓函式有能力改 head—— 這也是為什麼參數型別是struct node **。 - 測資含兩個 19：輸出可見第二個 19 插在第一個後面（
<的效果）。 - 易錯處：迴圈條件寫成
(*pp)->value < value && *pp != NULL——順序反了，*pp為 NULL 時先解參考，當機。 短路求值的檢查順序是安全性的一部分。
範例輸出
insertion sort by repeated insert_sorted:
input: 42 -7 19 0 88 -3 19 5
after insert 42: 42
after insert -7: -7 42
after insert 19: -7 19 42
after insert 0: -7 0 19 42
after insert 88: -7 0 19 42 88
after insert -3: -7 -3 0 19 42 88
after insert 19: -7 -3 0 19 19 42 88
after insert 5: -7 -3 0 5 19 19 42 88
sorted: -7 -3 0 5 19 19 42 88
after -100, 999: -100 -7 -3 0 5 19 19 42 88 999練習 4：合併兩條已排序串列（難度：進階）
題目
實作 struct node *list_merge(struct node *a, struct node *b)：
把兩條遞增串列合併成一條，不配置新節點、不複製資料，
只重接 next 指標。要求 O(m+n) 時間、O(1) 額外空間、
穩定（相等時 a 的元素在前）。
測資：a = 1 4 6 10 15、b = 2 3 6 7 20 30；
另測「與空串列合併」。
解題思路
- 這是 merge sort 的合併步驟，但串列版比陣列版優雅： 陣列合併需要輔助陣列，串列只要改指標。
- 核心迴圈：每步比較 a、b 目前的頭，較小者摘下來接到 結果尾端：
a: 1 ─> 4 ─> 6 結果: (空)
b: 2 ─> 3 ─> 7
1 <= 2 → 接 1；a 前進
a: 4 ─> 6 結果: 1
2 < 4 → 接 2；b 前進 …以此類推- 「第一個節點」的特例：結果串列一開始沒有尾巴可接。
dummy 節點技巧：在堆疊上放一個假頭
struct node dummy，tail從&dummy出發，每次都是tail->next = ...—— 零特例。最後回傳dummy.next（真正的頭）。 dummy 不用 malloc（函式結束自動消失），它的 value 從不使用。 - 收尾：一邊耗盡後，另一邊整段接上（
tail->next = a ?: b的語意）——串列的殺手級優勢，陣列版要逐個搬。 - 穩定性：比較用
<=，相等時取 a——排序演算法的穩定性 由合併的這個小於等於決定。 - 所有權轉移：合併後 a、b 的節點全進了結果串列， 原本的頭指標不可再使用（也不可分開 free——會 double free）。
參考解答
/*
* ex4_list_merge.c — 練習 4：合併兩條已排序串列（只改指標）
*
* 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex4_list_merge.c
* 執行：/tmp/out
*
* list_merge(a, b)：把兩條遞增串列合併成一條，不配置新節點、
* 不複製資料，只重接 next 指標。O(m+n) 時間、O(1) 額外空間。
* 技巧：dummy（啞）節點消除「第一個節點」的特例。
*/
#include <stdio.h>
#include <stdlib.h>
struct node {
int value;
struct node *next;
};
static struct node *new_node(int value)
{
struct node *n = malloc(sizeof *n);
if (n == NULL) {
fprintf(stderr, "out of memory\n");
exit(1);
}
n->value = value;
n->next = NULL;
return n;
}
/* 從陣列建有序串列（測資本身已排序） */
static struct node *from_array(const int *a, size_t n)
{
struct node *head = NULL, **pp = &head;
for (size_t i = 0; i < n; i++) {
*pp = new_node(a[i]);
pp = &(*pp)->next;
}
return head;
}
/*
* 合併：每一步從 a、b 的頭挑較小者接到結果尾端。
* dummy 節點是棧上的假頭：讓「接第一個節點」與「接後續節點」
* 都是 tail->next = ...，一個特例都沒有。
* 相等時取 a（保持穩定性：a 的元素排在 b 的前面）。
*/
static struct node *list_merge(struct node *a, struct node *b)
{
struct node dummy; /* 不 malloc：只是暫時的接頭點 */
struct node *tail = &dummy;
dummy.next = NULL;
while (a != NULL && b != NULL) {
if (a->value <= b->value) { /* <=：穩定合併 */
tail->next = a;
a = a->next;
} else {
tail->next = b;
b = b->next;
}
tail = tail->next;
}
/* 有一邊耗盡：另一邊整段接上（串列版不用逐一搬） */
tail->next = (a != NULL) ? a : b;
return dummy.next; /* 真正的頭在 dummy 後面 */
}
static void print_list(const char *tag, const struct node *head)
{
printf("%s", tag);
for (const struct node *p = head; p != NULL; p = p->next)
printf(" %d", p->value);
printf("\n");
}
static void free_list(struct node *head)
{
while (head != NULL) {
struct node *next = head->next;
free(head);
head = next;
}
}
int main(void)
{
int va[] = { 1, 4, 6, 10, 15 };
int vb[] = { 2, 3, 6, 7, 20, 30 };
struct node *a = from_array(va, sizeof va / sizeof va[0]);
struct node *b = from_array(vb, sizeof vb / sizeof vb[0]);
print_list("a :", a);
print_list("b :", b);
struct node *merged = list_merge(a, b);
print_list("merged:", merged);
/* 注意：a、b 的節點已全數併入 merged，原頭指標不可再用 */
/* 邊界：與空串列合併 */
struct node *c = from_array((int[]){ 5, 9 }, 2);
struct node *m2 = list_merge(c, NULL);
print_list("merge with empty:", m2);
free_list(merged); /* 釋放一次即可：節點沒有重複 */
free_list(m2);
return 0;
}程式碼講解
dummy放在堆疊上：它只是「接頭點」，函式回傳前取出dummy.next後就功成身退——不佔 heap、不用釋放。- 迴圈體四行 × 2 分支 + 尾段一行，就是完整的合併； 對照練習 3 的指標的指標，dummy 是另一種消特例手法 （加一個假物件 vs 加一層間接）。
- 測資兩邊各有一個 6：輸出
... 6 6 7 ...，a 的 6 在前 （用<=的證據）。 free_list(merged)一次釋放全部——因為節點沒有複製、 沒有共享，每個節點恰好被結果串列擁有一次。- 易錯處一：忘記最後接上殘餘段，尾段資料無聲消失。
- 易錯處二：合併後又對舊頭 a 呼叫 free_list——同一批節點 釋放兩次（double free），未定義行為。
範例輸出
a : 1 4 6 10 15
b : 2 3 6 7 20 30
merged: 1 2 3 4 6 6 7 10 15 20 30
merge with empty: 5 9練習 5：Floyd 龜兔賽跑偵測環（難度：進階）
題目
實作 int has_cycle(const struct node *head)：用 Floyd
龜兔賽跑演算法偵測串列是否帶環（O(n) 時間、O(1) 空間）。
自建一條帶環串列測試（尾節點指回中間節點），
測完把環拆掉再釋放。邊界：空串列、單節點、自環。
解題思路
- 為什麼是問題：帶環串列的走訪永不終止——
for (p = head; p; p = p->next)變成無窮迴圈， free_list 也會爆炸。偵測環是操作「來路不明串列」的前置檢查。 - 笨方法：走訪時把看過的節點存進集合，重複出現即有環—— O(n) 空間。Floyd 的精妙在 O(1) 空間。
- 龜兔賽跑：慢指標每輪 1 步、快指標每輪 2 步。 - 無環：快指標（或它的 next）先撞到 NULL，結束； - 有環：兩者遲早都進環。進環後把「快追慢」看成相對運動—— 快指標每輪拉近 1 步，距離嚴格遞減，必定相遇 （每輪縮 1 不可能「跳過」）。
0 ─> 1 ─> 2 ─> 3 ─> 4 ─> 5
^______________| （5 指回 2，環長 4）- 迴圈條件：
fast != NULL && fast->next != NULL—— fast 要跳兩步，兩步都要先確認存在；相遇判斷slow == fast比的是位址（同一個節點），不是值。 - 拆環再釋放：帶環串列不能直接走訪 free。 測試程式自己造的環自己知道接點（tail->next = NULL 即拆）； 真實場景要先找出環的入口（Floyd 第二階段，延伸閱讀）。
- 邊界：空串列（fast 起手就是 NULL）、單節點無環 （fast->next 是 NULL）、自環（node->next = node， 第一輪 slow == fast）——三個都要測。
參考解答
/*
* ex5_floyd_cycle.c — 練習 5：Floyd 龜兔賽跑偵測環
*
* 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex5_floyd_cycle.c
* 執行：/tmp/out
*
* has_cycle：慢指標走 1 步、快指標走 2 步；
* 有環必相遇、無環快指標先到 NULL。O(n) 時間、O(1) 空間。
* 自建帶環串列測試，測完拆環再釋放（帶環串列不能直接 free 走訪）。
*/
#include <stdio.h>
#include <stdlib.h>
struct node {
int value;
struct node *next;
};
static struct node *new_node(int value)
{
struct node *n = malloc(sizeof *n);
if (n == NULL) {
fprintf(stderr, "out of memory\n");
exit(1);
}
n->value = value;
n->next = NULL;
return n;
}
/*
* Floyd 龜兔賽跑。
* 迴圈不變量：fast 永遠在 slow 前面（或相遇）。
* 若有環：兩者都進環後，fast 每輪拉近 1 步，必相遇（不會跳過）。
* 若無環：fast 或 fast->next 先變 NULL，回報無環。
*/
static int has_cycle(const struct node *head)
{
const struct node *slow = head;
const struct node *fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next; /* 龜：1 步 */
fast = fast->next->next; /* 兔：2 步 */
if (slow == fast)
return 1; /* 相遇 = 有環 */
}
return 0; /* 兔子撞到 NULL = 無環 */
}
/* 建一條 0..n-1 的直串列，回傳頭；tail_out 給呼叫端拿尾節點 */
static struct node *make_list(int n, struct node **tail_out)
{
struct node *head = NULL, **pp = &head, *last = NULL;
for (int i = 0; i < n; i++) {
*pp = new_node(i);
last = *pp;
pp = &(*pp)->next;
}
*tail_out = last;
return head;
}
static struct node *nth(struct node *head, int idx)
{
while (idx-- > 0)
head = head->next;
return head;
}
static void free_list(struct node *head)
{
while (head != NULL) {
struct node *next = head->next;
free(head);
head = next;
}
}
int main(void)
{
printf("=== straight list: no cycle expected ===\n");
struct node *tail;
struct node *a = make_list(6, &tail);
printf(" 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL\n");
printf(" has_cycle = %s\n", has_cycle(a) ? "yes" : "no");
printf("\n=== make a cycle: tail(5) points back to node 2 ===\n");
/*
* 0 -> 1 -> 2 -> 3 -> 4 -> 5
* ^______________|
*/
struct node *entry = nth(a, 2);
tail->next = entry; /* 造環 */
printf(" has_cycle = %s\n", has_cycle(a) ? "yes" : "no");
printf("\n=== break the cycle, then free safely ===\n");
tail->next = NULL; /* 拆環：不拆就不能走訪釋放 */
printf(" has_cycle after break = %s\n", has_cycle(a) ? "yes" : "no");
free_list(a);
printf(" freed 6 nodes.\n");
printf("\n=== edge cases ===\n");
printf(" empty list : %s\n", has_cycle(NULL) ? "yes" : "no");
struct node *one = new_node(42);
printf(" single node : %s\n", has_cycle(one) ? "yes" : "no");
one->next = one; /* 自環 */
printf(" self-loop : %s\n", has_cycle(one) ? "yes" : "no");
one->next = NULL;
free(one);
return 0;
}程式碼講解
- 兩個指標從同一起點出發，但先走再比（
slow = ...; fast = ...; if (slow == fast)）——若先比，起點相同會立刻誤判有環。 fast->next->next前迴圈條件已保證fast與fast->next皆非 NULL——條件與迴圈體是一組不可拆的契約。- 測試流程「造環 → 偵測 → 拆環 → 釋放」順序不能亂： 拆環前 free_list 會走訪到已釋放節點（環讓它繞回來）。
- 自環測試
one->next = one後記得one->next = NULL再 free ——雖然 free 單一節點不走訪，但把懸空自指清掉是好習慣。 - 易錯處：迴圈條件只檢查
fast != NULL——奇數長度的無環串列 會在fast->next->next解參考 NULL 當機。
範例輸出
=== straight list: no cycle expected ===
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
has_cycle = no
=== make a cycle: tail(5) points back to node 2 ===
has_cycle = yes
=== break the cycle, then free safely ===
has_cycle after break = no
freed 6 nodes.
=== edge cases ===
empty list : no
single node : no
self-loop : yes練習 6：LRU 快取骨架（難度：挑戰）
題目
用雙向串列實作 LRU（最近最少使用）快取骨架，容量固定為 3：
lru_get(key)：命中時把節點搬到頭部並回傳值，未命中回 -1；lru_put(key, value)：已存在則更新並搬頭；新 key 且已滿時 淘汰尾部（最久未用）再插入；- 展示一段存取序列造成的淘汰過程，每步印出快取內容 （MRU→LRU 順序）與淘汰事件。
解題思路
- LRU 的兩個操作需求： - 「這個節點剛被用過」→ 把它搬到某個「最近」端： 需要從中間摘除節點——單向串列摘除要知道前驅（O(n)）， 雙向串列 O(1) 自摘，這就是用雙向的理由； - 「淘汰最久未用」→ 直接拿尾巴。
- 不變量：串列順序 = 使用時間順序（頭最新、尾最舊）。 get/put 每次都透過「摘下 + 掛頭」維持它。
head(MRU) tail(LRU)
┌─────┐ ┌─────┐ ┌─────┐
│ 3:30│<─>│ 2:20│<─>│ 1:10│ get(1) 之後：
└─────┘ └─────┘ └─────┘
┌─────┐ ┌─────┐ ┌─────┐
│ 1:10│<─>│ 3:30│<─>│ 2:20│ 1 搬到頭部
└─────┘ └─────┘ └─────┘- 摘除的四條線：雙向節點摘除要接好 prev/next 兩側， 且 e 是頭（prev 為 NULL）或尾（next 為 NULL）時要改 head/tail——四種組合寫成兩組 if/else 即可（見 unlink_entry）。
- put 的三條路：命中（更新+搬頭）；未命中且滿（淘汰尾+插入）； 未命中未滿（直接插入）。淘汰時印出 victim 的 key， 輸出軌跡讓策略行為可驗證。
- 教學版的妥協：find 用線性掃描 O(n)。生產版加一張 key→節點的雜湊表，get/put 全 O(1)——LeetCode 146 的完整解， 也是 09-hash-tables 的自然延伸。
- 記憶體：節點在 put 時 malloc、在淘汰或 lru_free 時 free， 一進一出配對清楚。
參考解答
/*
* ex6_lru_cache.c — 練習 6：LRU 快取骨架（雙向串列）
*
* 編譯：cc -std=c11 -Wall -Wextra -o /tmp/out ex6_lru_cache.c
* 執行：/tmp/out
*
* LRU（Least Recently Used）淘汰策略：
* - 雙向串列維持「最近使用在頭、最久未用在尾」
* - 存取（get/put 命中）：節點搬到頭部
* - 放入新項目且已滿：淘汰尾部節點
* 本骨架查找用 O(n) 線性掃描（教學版）；
* 生產版會加雜湊表 key->node 讓查找也是 O(1)（見 09-hash-tables）。
*/
#include <stdio.h>
#include <stdlib.h>
struct entry {
int key;
int value;
struct entry *prev;
struct entry *next;
};
struct lru {
struct entry *head; /* 最近使用 */
struct entry *tail; /* 最久未用（淘汰對象） */
int size;
int capacity;
};
static void lru_init(struct lru *c, int capacity)
{
c->head = c->tail = NULL;
c->size = 0;
c->capacity = capacity;
}
/* 把節點從串列摘下（不釋放）：雙向串列 O(1) 自摘 */
static void unlink_entry(struct lru *c, struct entry *e)
{
if (e->prev != NULL) e->prev->next = e->next;
else c->head = e->next; /* e 是頭 */
if (e->next != NULL) e->next->prev = e->prev;
else c->tail = e->prev; /* e 是尾 */
e->prev = e->next = NULL;
}
/* 掛到頭部（最近使用位置） */
static void push_head(struct lru *c, struct entry *e)
{
e->prev = NULL;
e->next = c->head;
if (c->head != NULL)
c->head->prev = e;
c->head = e;
if (c->tail == NULL) /* 原本是空的 */
c->tail = e;
}
/* 線性查找 key（教學版；生產版用雜湊表加速） */
static struct entry *find(struct lru *c, int key)
{
for (struct entry *e = c->head; e != NULL; e = e->next)
if (e->key == key)
return e;
return NULL;
}
/* get：命中就搬到頭部並回傳值；未命中回 -1 */
static int lru_get(struct lru *c, int key)
{
struct entry *e = find(c, key);
if (e == NULL)
return -1;
unlink_entry(c, e); /* 摘下再掛頭 = 「最近使用」 */
push_head(c, e);
return e->value;
}
/* put：已存在則更新並搬頭；不存在則插入，滿了先淘汰尾部 */
static void lru_put(struct lru *c, int key, int value)
{
struct entry *e = find(c, key);
if (e != NULL) {
e->value = value;
unlink_entry(c, e);
push_head(c, e);
return;
}
if (c->size == c->capacity) { /* 滿了：淘汰最久未用 */
struct entry *victim = c->tail;
printf(" [evict key=%d]\n", victim->key);
unlink_entry(c, victim);
free(victim);
c->size--;
}
e = malloc(sizeof *e);
if (e == NULL) {
fprintf(stderr, "out of memory\n");
exit(1);
}
e->key = key;
e->value = value;
e->prev = e->next = NULL;
push_head(c, e);
c->size++;
}
/* 從頭到尾印出（頭 = 最近使用） */
static void lru_dump(const struct lru *c)
{
printf(" cache (MRU->LRU):");
for (const struct entry *e = c->head; e != NULL; e = e->next)
printf(" (%d:%d)", e->key, e->value);
printf("\n");
}
static void lru_free(struct lru *c)
{
struct entry *e = c->head;
while (e != NULL) {
struct entry *next = e->next;
free(e);
e = next;
}
c->head = c->tail = NULL;
c->size = 0;
}
int main(void)
{
struct lru cache;
lru_init(&cache, 3); /* 容量 3 */
printf("LRU cache, capacity = 3\n\n");
printf("put(1,10) put(2,20) put(3,30):\n");
lru_put(&cache, 1, 10);
lru_put(&cache, 2, 20);
lru_put(&cache, 3, 30);
lru_dump(&cache);
printf("\nget(1) -> touches key 1, moves it to front:\n");
printf(" get(1) = %d\n", lru_get(&cache, 1));
lru_dump(&cache);
printf("\nput(4,40) -> cache full, evicts LRU (key 2):\n");
lru_put(&cache, 4, 40);
lru_dump(&cache);
printf("\nget(2) -> was evicted:\n");
printf(" get(2) = %d (miss)\n", lru_get(&cache, 2));
printf("\nput(3,99) -> update existing key, moves to front:\n");
lru_put(&cache, 3, 99);
lru_dump(&cache);
printf("\nput(5,50) -> evicts key 1 (now the LRU):\n");
lru_put(&cache, 5, 50);
lru_dump(&cache);
lru_free(&cache);
return 0;
}程式碼講解
unlink_entry+push_head是整個 LRU 的原子操作對： 「摘下再掛頭」四個字就是 LRU 策略的全部。兩個函式各自維護 head/tail 的邊界情況，組合起來便處處正確。- 「搬到頭部」不配置新節點——搬的是指標不是資料， 這是串列相對陣列的本質優勢（陣列版搬頭要 memmove 整段）。
- 淘汰訊息印在 put 內部：對快取這種「行為重於結果」的結構， 把內部事件輸出成軌跡是最好的測試方式。
- 存取序列的設計有意圖：
get(1)把 1 救活，隨後put(4)淘汰的就變成 2（而不是最早插入的 1）——證明淘汰的是 「最久未用」而非「最早插入」（那是 FIFO）。 - 易錯處一：unlink 忘了處理「e 是尾」的情況，tail 懸空， 下次淘汰 free 到已摘除的節點。
- 易錯處二：put 對已存在的 key 走「插入」路徑， 造成同 key 兩個節點——find-first 掩蓋問題，直到淘汰時錯亂。
範例輸出
LRU cache, capacity = 3
put(1,10) put(2,20) put(3,30):
cache (MRU->LRU): (3:30) (2:20) (1:10)
get(1) -> touches key 1, moves it to front:
get(1) = 10
cache (MRU->LRU): (1:10) (3:30) (2:20)
put(4,40) -> cache full, evicts LRU (key 2):
[evict key=2]
cache (MRU->LRU): (4:40) (1:10) (3:30)
get(2) -> was evicted:
get(2) = -1 (miss)
put(3,99) -> update existing key, moves to front:
cache (MRU->LRU): (3:99) (4:40) (1:10)
put(5,50) -> evicts key 1 (now the LRU):
[evict key=1]
cache (MRU->LRU): (5:50) (3:99) (4:40)常見錯誤解法對照
| 錯誤寫法 | 症狀 | 正解 |
|---|---|---|
free(p); p = p->next; |
use-after-free | 先存 next 再 free（練習 1） |
| push_front 空串列不設 tail | 之後 push_back 接錯位置 | 空串列兩指標都設（練習 2） |
條件寫 (*pp)->value < v && *pp |
NULL 解參考當機 | 先判 NULL 再解參考（練習 3） |
| 合併後忘接殘餘段 | 尾段資料消失 | tail->next = a ? a : b（練習 4） |
Floyd 只檢查 fast != NULL |
奇數長度串列當機 | 同時檢查 fast->next（練習 5） |
| 帶環串列直接 free_list | 無窮迴圈／二次釋放 | 先拆環再釋放（練習 5） |
| LRU 淘汰「最早插入」 | 是 FIFO 不是 LRU | get 也要搬頭（練習 6） |