17｜鏈結串列

還沒完成C 或 C++ 皆可CPU 時間上限 1 秒計算 heap 用量

題目說明

C 或 C++ 皆可｜CPU 時間上限 1 秒｜計算 heap 用量，有記憶體洩漏就不通過

題目

自己做一個單向鏈結串列（singly linked list）：每個節點存一個整數和一個指向下一個節點的指標，最後一個節點的 next 是 NULL（C++ 是 nullptr）。

head ──▶ [ 0 | ●─]──▶ [ 1 | ●─]──▶ [ 2 | NULL ]

一開始串列是空的（head 是 NULL）。依序執行輸入的指令：

指令	動作	輸出
`push_front x`	把 x 加到最前面	無
`push_back x`	把 x 加到最後面	無
`pop_front`	移除最前面的節點	串列是空的：輸出 `empty`；否則輸出被移除的值
`remove x`	移除第一個值等於 x 的節點	找不到 x：輸出 `not found`；找到並移除：不輸出
`reverse`	把整個串列就地反轉（改節點的 `next` 指標，不要建立新節點）	無
`print`	從頭到尾輸出所有值，以一個空白分隔	串列是空的：輸出 `empty`

規定：

每個節點都要自己配置：C 用 malloc，C++ 用 new。被移除的節點要馬上釋放（free / delete）。
程式結束前要釋放串列裡剩下的所有節點，否則檢查會得到「記憶體洩漏」。
C++ 不要用 std::list、std::forward_list、std::vector、std::deque 等容器來存資料——這一題的重點就是自己用指標串起節點、自己管理記憶體。（檢查程式看不出來，請自己遵守。）

輸入

每行一個指令，格式如上表，指令名稱和數字之間有一個空白。
指令最多 20000 個（也可能完全沒有指令），一直讀到輸入結束（EOF）為止。
每個 x 都是整數，−1000000000 ≤ x ≤ 1000000000。

輸出

只有 pop_front、remove（找不到時）和 print 會輸出，每次輸出一行，格式如上表。

範例

輸入：

push_back 1
push_back 2
push_front 0
push_back 1
print
remove 1
print
remove 5
reverse
print
pop_front
pop_front
pop_front
pop_front
print
push_back 7
print

輸出：

0 1 2 1
0 2 1
not found
1 2 0
1
2
0
empty
empty
7

說明：remove 1 只移除第一個 1，所以 0 1 2 1 變成 0 2 1。最後串列裡還剩一個 7，程式結束前要記得釋放它。

複習重點

共通：

用 struct 表示節點，節點裡有一個指向「同一種 struct」的指標
p->value 是 (*p).value 的簡寫：透過指標存取 struct 的欄位
想讓函式修改呼叫端的指標變數（例如 head），要傳「指標的位址」，也就是指標的指標
釋放節點之前，先把之後還需要的東西（例如 next）存起來；釋放之後就不能再碰那個節點
每一個配置的節點最後都要剛好釋放一次

C：

struct node { int value; struct node *next; };，用 malloc(sizeof *n) 配置、free(n) 釋放
修改 head 的函式參數寫成 struct node **head，呼叫時傳 &head，函式裡用 *head 讀寫

C++：

struct Node { int value; Node *next; };，用 new Node{x, nullptr} 配置、delete n 釋放（new 對 delete，new[] 對 delete[]，不能和 malloc / free 混用）
修改 head 的函式參數可以寫成指標的參考 Node *&head，呼叫時直接傳 head
第 19 題會學到用 std::unique_ptr 讓節點自動釋放，完全不用寫 delete

提示 1：節點和 push_front

struct node {
    int value;
    struct node *next;
};

void push_front(struct node **head, int x) {
    struct node *n = malloc(sizeof *n);
    n->value = x;
    n->next = *head;   // 新節點接在原本的第一個前面
    *head = n;         // 改 main 裡的 head：所以才需要傳 &head 進來
}

push_back 要先從 head 一路走到最後一個節點（next 是 NULL 的那個），把新節點接在它後面；串列是空的時候要另外處理（直接讓 *head 指向新節點）。

提示 2：remove 要記住「前一個」節點

單向串列只能往後走，要移除 cur 時，必須修改它前一個節點的 next。所以走的時候同時記住 prev：

找到 cur 之後，如果 prev 是 NULL，表示要移除的是第一個節點，改的是 *head；否則改 prev->next。
先把 cur 從串列中拆下來，最後才 free(cur)。

如果釋放之後又用到那個節點，按 Ctrl+Shift+B 檢查時，第一階段的 AddressSanitizer 會報告 heap-use-after-free，並指出是哪一行。

提示 3：reverse 和釋放整個串列

反轉用三個指標 prev（一開始是 NULL）、cur（一開始是 head）、next：每一步先存好 next = cur->next，再把 cur->next 改成指向 prev，然後 prev、cur 都往前移一步。最後 prev 就是新的 head。建議先在紙上畫 3 個節點的箭頭變化。

釋放整個串列時，free(cur); cur = cur->next; 是錯的（釋放之後才讀 cur->next）。要先存 next，再釋放。

練習時想看有沒有漏掉沒釋放的節點，可以在終端機輸入：

run exercises\3-memory\17-linked-list\main.c --mem --input exercises\3-memory\17-linked-list\tests\01.in

（C++ 就把 main.c 改成 main.cpp）。報告會列出沒有釋放的記憶體是在哪一行配置的。