# 2025q1 Homework1 (lab0)
contributed by < [LeoriumDev](https://github.com/LeoriumDev/) >
### Reviewed by horseface1110
q_remove_head 中
> 改進後的程式碼：
if (sp && bufsize && elem->value)
>>*(stpncpy(sp, elem->value, bufsize)) = '\0';
這樣寫，若elem->value大小剛好 = bufsize，最後一行會導致溢位。
> 已改進
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i5-7300HQ CPU @ 2.50GHz
CPU family: 6
Model: 158
Thread(s) per core: 1
Core(s) per socket: 4
Socket(s): 1
Stepping: 9
CPU(s) scaling MHz: 92%
CPU max MHz: 3500.0000
CPU min MHz: 800.0000
BogoMIPS: 4999.90
Virtualization features:
Virtualization: VT-x
Caches (sum of all):
L1d: 128 KiB (4 instances)
L1i: 128 KiB (4 instances)
L2: 1 MiB (4 instances)
L3: 6 MiB (1 instance)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0-3
```
## 佇列操作開發過程
### q_new
> Commit: [c7cb173](https://github.com/sysprog21/lab0-c/commit/c7cb1733cbae1e8af6fe2238d20c422477040c72)
#### 函式目標
建立新的「空」佇列
#### 實作說明
透過 `<stdlib.h>` 函式庫裡的 `malloc` 來配置一塊大小為 `list_head` 結構體的記憶體。如果記憶體配置失敗， `head` 會是空指標，利用此機制，使函式回傳 `NULL` 。若記憶體配置成功，則使用 [`<list.h>`](https://github.com/sysprog21/lab0-c/blob/master/list.h) 函式庫裡的 `INIT_LIST_HEAD` 來初始化 `head` ，也就是將 `head` 指向的前一個結構體 `prev` 及指向的下一個結構體 `next` 都指向 `head` 自己。
list_head 結構體示意圖：
```graphviz
digraph list_head {
rankdir=LR;
subgraph cluster_0 {
node [shape=record];
ptr [label="{<head>head node}|{<prev>prev|<next>next}"];
style=bold;
label="list_head"
}
}
```
函式功能示意圖：
```graphviz
digraph q_new {
rankdir=LR;
node [shape=record];
ptr [label="{<head>head node}|{<prev>prev|<next>next}"];
ptr:prev:w -> ptr:head:w[arrowhead=normal, arrowtail=normal, dir=one];
ptr:next:e -> ptr:head:w[arrowhead=normal, arrowtail=normal, dir=one];
}
```
#### 實作過程
一開始實作的時候是直接將 `head` 的 `prev` 及 `next` 指向 `head` 本身，來初始化佇列。後來參考 [王彥傑](https://hackmd.io/@yanjiew/linux2023q1-lab0#q_new) 同學的實作方式才發現 `<list.h>` 有 `INIT_LIST_HEAD` 這個函式，可簡化程式行數，加以利用。
改進程式碼：
```diff
...
- head->next = head;
- head->prev = head;
+ INIT_LIST_HEAD(head);
...
```
後來在閱讀 `<list.h>` 時，發現有 `LIST_HEAD` 這個巨集，其功能為定義及初始化環狀鏈結串列。原本想將其取代 `malloc` 那行程式，但想到物件的生命週期，`head` 的生命週期僅存在於 `q_new` 函式內，若使用這個巨集會使回傳的 `head` 無法使用，使用 `head` 會導致 undefined behavior。
> C99 規格書 6.2.4 - 2
>
> **If an object is referred to outside of its lifetime, the behavior is undefined.** The value of a pointer becomes indeterminate when the object it points to reaches the end of its lifetime.
### q_free
> Commit: [8cb27cd](https://github.com/sysprog21/lab0-c/commit/8cb27cd84af78055f6487e0c39baaa04eacbf45b)
#### 函式目標
釋放佇列所佔用的記憶體
#### 實作說明
若傳入的佇列是空的，則提前結束此函式的執行。之後利用 `list_for_each_entry_safe` 這個巨集來迭代每個 `element_t` 結構體，逐一釋放所佔用的記憶體。
`element_t` 結構體示意圖：
```graphviz
digraph element_t {
rankdir=LR;
subgraph cluster_0 {
style=bold;
label="element_t"
subgraph cluster_1 {
node [shape=record];
value [label="value", style=bold];
style=bold;
label="char *"
}
subgraph cluster_2 {
node [shape=record];
ptr [label="{<head>head node}|{<prev>prev|<next>next}"];
style=bold;
label="list_head"
}
value -> ptr [style=invis];
}
}
```
#### 實作過程
一開始覺得很奇怪，為什麼傳入的參數是 `struct list_head *head` 而不是 `struct element_t *elem` 呢？後來在研讀 [linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list) 才了解到 [container_of](https://hackmd.io/@sysprog/c-linked-list#container_of) 這個用法，其可傳入結構體的成員地址，利用 offsetof 函式，回傳此結構體的地址。可用來「提升程式碼的可攜性」。原本參考 [陳麒升](https://github.com/sysprog21/lab0-c/commit/a18fd45b8aec898b07f3d54d3160c4a9a40186c7) 同學的作法來實作 `element_t` 結構體的迭代，後來看到 [王彥傑](https://hackmd.io/@yanjiew/linux2023q1-lab0#q_free) 同學利用 `q_release_element` 函式來使程式碼變更簡潔了，從八行縮減為兩行，於是決定採用後者的做法。
改進程式碼：
```diff
...
- list_for_each_entry_safe(entry, safe, head, list) {
- if (!entry)
- return;
- list_del(&entry->list);
- if (!entry->value)
- free(&entry->value);
- free(entry);
- }
+ list_for_each_entry_safe(entry, safe, head, list)
+ q_release_element(entry);
...
```
此外，在閱讀 `<queue.h>` 標頭檔時，我有看到 `q_release_element` 的說明寫到：「使函式僅供內部使用。」(This function is intended for internal use only.) 我這時在思考這裡指的內部是指與老師評分系統有關還是我整個 `queue.c` 檔案也包含在其中，最後，我認為是後者，由於後來看到 `<harness.h>` 標頭檔，是專門用來評分的，但卻沒有將此函式放置於 `<harness.h>` 中，由此推估是可以使用的。
後來在比較兩者功能時，發現 `q_release_element` 使用的是 `test_free` 而非常見的 `<stdlib.h>` 中的 `free`，這讓我感到好奇，後來發現應是老師測試所需加的 wrapper。之後也發現 `<harness.h>` 中有巨集將 `free` 定義為 `test_free`，而非直接使用 `<stdlib.h>` 中的 `free`，由此巨集可知上述的擔憂是多餘的，其功能大致相同，甚至還幫你檢查輸入的指標是不是空指標，所以最後才選用 `q_release_element` 函式。
之後與 [莊永太](https://hackmd.io/@alex-c1234/) 同學討論，`list_del` 函式是否有必要性，最後是認定「沒有必要性」。莊永太同學是認為我改進後的程式碼沒有將迭代各個鏈結串列節點，將節點逐一從鏈結串列中移除 (remove)。這樣的疏忽會導致在使用 `list_head` 的 `prev` 及 `next` 成員所指向的節點已被釋放，讓存取成員的行為未定義。但由於在使用此函式是將「釋放佇列佔有的所有記憶體」，並不會也不應該在釋放後再次存取節點，所以我斷定不必要使用 `list_del` 函式。
### q_insert_head
> Commit: [bd2b8b1](https://github.com/sysprog21/lab0-c/commit/bd2b8b1392e0853ac0ab49e76289fc711a9b5b05)
#### 函式目標
在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則)
#### 實作說明
一開始先判斷傳入的結構體 `list_head` 及字串是否為空指標，若為空指標則回傳 `false` 代表記憶體配置失敗或是傳入的是空佇列。接著 `malloc` 一段大小為 `element_t` 的記憶體，若配置失敗，立即回傳 `false`。接著，由於在 `<queue.h>` 裡有提及此函式必須明確地配置記憶體，並將字串複製到裡面。所以，使用 `strdup` 函式來達成這個需求，若記憶體配置失敗，則先釋放剛剛配置的 `elem` 結構體，再回傳 `false`。讓記憶體配置及傳入的不是空佇列，則在佇列的頭部插入新元素，並回傳 `true`，表示操作成功。
對新佇列的函式操作示意圖：
```graphviz
digraph element_t {
rankdir=LR;
subgraph cluster_0 {
node [shape=record];
ptr_head [label="{<head>head node}|{<prev>prev|<next>next}"];
style=bold;
label="head";
}
subgraph cluster_1 {
style=bold;
label="first node";
subgraph cluster_2 {
node [shape=record];
value [label="value", style=bold];
style=bold;
label="char *";
}
subgraph cluster_3 {
node [shape=record];
ptr [label="{<head>head node}|{<prev>prev|<next>next}"];
style=bold;
label="list_head";
}
ptr:head -> value [style=invis];
}
ptr_head:next -> ptr:prev [dir=both];
ptr_head:prev -> ptr:next [dir=both];
}
```
對舊有佇列的函式操作示意圖：
```graphviz
digraph element_t {
rankdir=LR;
subgraph cluster_0 {
node [shape=record];
ptr_head [label="{<head>head node}|{<prev>prev|<next>next}"];
style=bold;
label="head";
}
subgraph cluster_1 {
node [shape=record];
ptr_1 [label="{<head>head node}|{<prev>prev|<next>next}"];
style=bold;
label="first node";
}
subgraph cluster_2 {
node [shape=record];
ptr_2 [label="{<head>head node}|{<prev>prev|<next>next}"];
style=bold;
label="second node";
}
ptr_head:next:e -> ptr_1:prev:w [dir=both];
ptr_1:next:e -> ptr_2:prev:w [dir=both];
ptr_head:prev:s -> ptr_2:next:s [dir=both];
}
```
```graphviz
digraph element_t {
rankdir=LR;
subgraph cluster_0 {
node [shape=record];
ptr_head [label="{<head>head node}|{<prev>prev|<next>next}"];
style=bold;
label="head";
}
subgraph cluster_1 {
node [shape=record];
ptr_1 [label="{<head>head node}|{<prev>prev|<next>next}"];
style="dashed";
color="red";
label="first node (new)";
}
subgraph cluster_2 {
node [shape=record];
ptr_2 [label="{<head>head node}|{<prev>prev|<next>next}"];
style=bold;
label="second node";
}
subgraph cluster_3 {
node [shape=record];
ptr_3 [label="{<head>head node}|{<prev>prev|<next>next}"];
style=bold;
label="third node";
}
ptr_head:next:t -> ptr_1:prev:t [dir=both];
ptr_1:next:t -> ptr_2:prev:t [dir=both];
ptr_2:next:t -> ptr_3:prev:t [dir=both];
ptr_head:prev:s -> ptr_3:next:s [dir=both];
}
```
> 為簡化示意圖，利用雙向箭頭來表達鏈結關係。
>
> 第二張圖移除了 `value`，為了專注於節點間的關係。特別需注意的是，`head` 並沒有 `value`，它不算是一個節點。
>
> 實際鏈結關係：
> (source: [Linked list 在 Linux 核心原始程式碼](https://hackmd.io/@sysprog/c-linked-list#Linked-list-在-Linux-核心原始程式碼))
#### 實作過程
一開始實作的時候，我並沒有如 `<queue.h>` 敘述所示，複製字串到新的記憶體空間。詳細閱讀 `<queue.h>` 才發現有這個要求，我原本要使用 `strncpy` 來複製字串，但在參考 [Ying-You Hong](https://hackmd.io/@willwillhi/lab0-2023#q_insert_head) 的實作後，發現有 `strdup` ([man page](https://man7.org/linux/man-pages/man3/strdup.3.html)) 這個函式可以使用，並且程式碼縮短了。後來在偷看 `<harness.h>` 發現 `test_strdup` 這個測試函式，理解到老師是預期我們去使用 `strdup` 這個函式。
改進程式碼：
```diff
...
- strncpy(elem->value, s, strlen(s));
- elem->value[strlen(s) - 1] = '\0';
+ elem->value = strdup(s);
...
```
之後，我在思考一個問題，就是要不要判斷傳入的字串是否為空指標，原本看到下面程式碼第二行的時候就大膽斷定「應該」是有檢查到吧？
```c=
elem->value = strdup(s);
if (!elem->value) {
free(elem);
return false;
}
```
但在我把這段程式碼抽絲剝繭後，我發現 `!elem->value` 僅是檢查 `strdup` 的所回傳的記憶體配置有無失敗，但卻沒有檢查到原本函式傳入的字串是否為空指標。根據 *C standard (ISO/IEC 9899:1999)* 中 7.21.1 - 2 發現「函式參數需為有效的數值」，接著再依據 7.1.4 - 1 中提及「若函式有無效的數值 (如空指標) 該函式會發生未定義的行為」。
> C99 規格書 7.21.1 - 2
> Where an argument declared as size_t n specifies the length of the array for a function, n can have the value zero on a call to that function. Unless explicitly stated otherwise in the description of a particular function in this subclause, ***pointer arguments on such a call shall still have valid values, as described in 7.1.4.*** On such a call, a function that locates a character finds no occurrence, a function that compares two character sequences returns zero, and a function that copies characters copies zero characters.
> C99 規格書 7.1.4 - 1
> Each of the following statements applies unless explicitly stated otherwise in the detailed descriptions that follow: ***If an argument to a function has an invalid value*** (such as a value outside the domain of the function, or a pointer outside the address space of the program, ***or a null pointer***, or a pointer to non-modifiable storage when the corresponding parameter is not const-qualified) or a type (after promotion) not expected by a function with variable number of arguments, ***the behavior is undefined***.
由上可知，若不判斷傳入的字串是否為空指標，有可能會導致 undefined behavior 的產生。因此，我在最後決定加入「判斷傳入的字串是否為空指標」的表達式。
改進程式碼：
```diff
...
- if (!head)
+ if (!head || !s)
return false;
...
```
(reference: [Is it guaranteed to be safe to perform memcpy(0,0,0)?](https://stackoverflow.com/questions/5243012/is-it-guaranteed-to-be-safe-to-perform-memcpy0-0-0))
### q_insert_tail
> Commit: [bd2b8b1](https://github.com/sysprog21/lab0-c/commit/bd2b8b1392e0853ac0ab49e76289fc711a9b5b05)
#### 函式目標
在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則)
#### 實作說明
由於本處的佇列為環狀雙向鏈結串列，可將傳入的 `head` 指向前一個節點 (如下圖紅色箭頭)，也就是此佇列的尾部，利用 `list_add` 的特性 (會在 `head` 後直接插入節點)，將此佇列的尾部 (second node) 當成 `head`，如此一來就會在此佇列的尾部及頭部插入一個節點，進而達到在佇列尾部插入新節點的功能。
函式操作示意圖：
```graphviz
digraph element_t {
rankdir=LR;
subgraph cluster_0 {
node [shape=record];
ptr_head [label="{<head>head node}|{<prev>prev|<next>next}"];
style=bold;
label="head";
}
subgraph cluster_1 {
node [shape=record];
ptr_1 [label="{<head>head node}|{<prev>prev|<next>next}"];
style=bold;
label="first node";
}
subgraph cluster_2 {
node [shape=record];
ptr_2 [label="{<head>head node}|{<prev>prev|<next>next}"];
style=bold;
label="second node";
}
ptr_head:next:e -> ptr_1:prev:w [dir=both];
ptr_1:next:e -> ptr_2:prev:w [dir=both];
ptr_head:prev:s -> ptr_2:next:s [dir=both];
ptr_head:prev:n -> ptr_2:head:n [color=red];
}
```
```graphviz
digraph element_t {
rankdir=LR;
subgraph cluster_0 {
node [shape=record];
ptr_head [label="{<head>head node}|{<prev>prev|<next>next}"];
style=bold;
label="head";
}
subgraph cluster_1 {
node [shape=record];
ptr_1 [label="{<head>head node}|{<prev>prev|<next>next}"];
style=bold;
label="first node";
}
subgraph cluster_2 {
node [shape=record];
ptr_2 [label="{<head>head node}|{<prev>prev|<next>next}"];
style=bold;
label="second node";
}
subgraph cluster_3 {
node [shape=record];
ptr_3 [label="{<head>head node}|{<prev>prev|<next>next}"];
style="dashed";
color="red"
label="third node (new)";
}
ptr_head:next:t -> ptr_1:prev:t [dir=both];
ptr_1:next:t -> ptr_2:prev:t [dir=both];
ptr_2:next:t -> ptr_3:prev:t [dir=both];
ptr_head:prev:s -> ptr_3:next:s [dir=both];
}
```
#### 實作過程
原本是想說直接複製 `q_insert_head` 然後把 `list_add` 改成 `list_add_tail`，但是我認為程式碼過於重複 ([DRY](https://en.wikipedia.org/wiki/Don%27t_repeat_yourself))，於是在參考 `<list.h>` 中 `list_add_tail` 的做法後，
```c
struct list_head *prev = head->prev;
```
直接將重複的程式碼刪掉，換成下方這行簡潔有力的程式碼。
```c
return q_insert_head(head->prev, s);
```
後來為避免不必要的函式呼叫，加入下方這段程式來先判斷是否傳入空指標，提前結束函式執行。
```c
if (!head || !s)
return false;
```
### q_remove_head
> Commit: [18cee40](https://github.com/sysprog21/lab0-c/commit/18cee408b46a8ba172693e13dc33b28ed8861975)
#### 函式目標
在佇列開頭 (head) 移去 (remove) 給定的節點
#### 實作說明
一開始先檢查 `head` 是否為空指標或是輸入佇列是空的。利用 `list_first_entry` 巨集得到佇列的第一個節點，用 `list_del` 將其從鏈結串列中刪除。接著要將 `element_t` 中的 `value` 存入 `sp` 當中。一開始需先檢查 `sp` 是否為空指標及 `bufsize` 是否為 0，之後看 `elem` 結構體中的 `value` 成員是否為空指標。之後利用 `strndup` 來複製字串並存入 `sp` 中。
#### 實作過程
在將刪除元素的數值存到 `sp` 時，我原先是使用下面這段實作
```c
if (!sp || !bufsize)
return elem;
strncpy(sp, elem->value, bufsize);
sp[bufsize - 1] = '\0';
```
後來我在思考如何更精簡程式碼，於是改成下面這段程式碼，為避免 `elem->value` 為空指標，所以在上面 `if` 判斷式添增 `elem->value` 的判斷。在查閱 `string_copying` 的 [man page](https://man7.org/linux/man-pages/man7/string_copying.7.html) 的時候看到 `strlcpy` 有提供 `truncation` 的功能，可以不用在字串大於 `sp` 大小的時候，手動添加 null terminator。但由於這個函數於手冊裡提及可能會導致 DoS (Denial of Service) 攻擊，所以先不考慮使用。後續研讀手冊時發現，裡面有提及 `stpcpy` 比 `strcpy` 快很多，所以可想而知 `stpncpy` 會比 `strncpy` 來的快。`stpncpy` 會回傳「指向目標 (destination) 字串的最後一個字元」的指標，可以直接將最後一個字元設為 `\0`，所以最後使用 `stpncpy` 來實作。
改進後的程式碼：
```c
if (sp && bufsize && elem->value)
*(stpncpy(sp, elem->value, bufsize)) = '\0';
```
改進程式碼
> (Reviewed by horseface1110)
> q_remove_head 中
> > 改進後的程式碼：
> if (sp && bufsize && elem->value)
> >> *(stpncpy(sp, elem->value, bufsize)) = '\0';
>
> 這樣寫，若elem->value大小剛好 = bufsize，最後一行會導致溢位。
>
> Commit: [c5899ac](https://github.com/sysprog21/lab0-c/commit/c5899ac3db48301d59a72927d4f94c82d682759b)
```diff
- if (sp && bufsize && elem->value)
- *(stpncpy(sp, elem->value, bufsize)) = '\0';
+ if (sp && bufsize && elem->value) {
+ strncpy(sp, elem->value, bufsize - 1);
+ sp[bufsize - 1] = '\0';
+ }
```
### q_remove_tail
> Commit: [18cee40](https://github.com/sysprog21/lab0-c/commit/18cee408b46a8ba172693e13dc33b28ed8861975)
#### 函式目標
在佇列尾端 (tail) 移去 (remove) 給定的節點
#### 實作說明
首先，先檢查佇列是否為 `NULL` 及是否為空佇列。用 `prev` 成員指到上上一個節點，將最後一個節點刪除。
#### 實作過程
這裡是利用之前 `q_insert_tail` 的想法，回傳 `head` 版本的實作，以減少行數。這裡使用 `head->prev->prev` 的原因是，是刪除最後一個節點，而不是在最後一個節點與頭部之間插入節點，所以先指到倒數第二個節點當成 `head`，利用 `list_first_entry` 來得到最後一個節點，然後從佇列中移除，將移除的佇列資料存入 output buffer。
### q_size
> Commit: [7d5e7e4](https://github.com/sysprog21/lab0-c/commit/7d5e7e4d9e06f9e952d95a2073aa75ca0a8072ab)
#### 函式目標
計算目前佇列的節點總量
#### 實作說明
首先，先檢查佇列是否為 `NULL` 及是否為空佇列。接著利用 `list_for_each` 巨集來迭代所有節點，利用變數加總數量，回傳節點數。
#### 實作過程
在之前查閱 `<list.h>` 的時候就有看到 `list_for_each` 這個巨集，在實作的時候馬上回想起，將其用於實作。
### q_delete_mid
> Commit: [e0c08f9](https://github.com/sysprog21/lab0-c/commit/e0c08f971afba273132c144187ea6cf6a1a2fab6)
#### 函式目標
移走佇列中間的節點，詳見 [LeetCode 2095. Delete the Middle Node of a Linked List](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/description/)
#### 實作說明
首先，先判斷佇列是否為 `NULL` 或空佇列。接著利用兩個指標 (左與右) 朝中間尋找，如果這兩個指標有指到同一個節點 (佇列大小為奇數) 或是左指標的下一個指標為右指標 (佇列大小為偶數)，則結束迴圈，將該節點從佇列刪除，釋放其所佔用的記憶體。
#### 實作過程
一開始我是想用 `q_size` 來獲得佇列大小，然後除以二作為計數器，每次訪問扣一，若計數器為零代表到中間的節點了。但是後來想到 `list_head` 是環狀鏈結串列，可以利用兩個指標來找到中間的節點，於是換成後者的實作方式。
### q_delete_dup
> Commit: [7d2229c](https://github.com/sysprog21/lab0-c/commit/7d2229c374b8c75ceb38925e285aa9b937a9e077)
#### 函式目標
在已經排序的狀況，移走佇列中具備重複內容的節點，詳見 [LeetCode 82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)
#### 實作說明
首先，先檢查佇列是否為 `NULL` 或空佇列。然後利用 `list_for_each_entry_safe` 來迭代每一個節點，如果 `safe` 指標指到 `head` 代表已經走訪過所有節點或此佇列僅有單一節點，則不會執行判別式。要判斷是否有重複內容的節點可以用 `strcmp`，由於 `strcmp` 在兩個字串相同的情況下會回傳 `0` 所以要加 `!` (NOT) 來反轉表達式。在確定 `safe` 指標並沒有指到 `head` 及兩節點句有重複內容時，利用 `list_del` 巨集來將節點從佇列中移除，之後利用 `q_release_element` 來釋放記憶體。上述做法會留下一個重複的內容，但 `<queue.h>` 有提及「...僅於佇列中留下獨特的字串」(...leaving only distinct strings from the original queue)，所以還要判斷這種情況：
```c
["a", "a", "a", "b"]
```
如果有一個佇列如上，說明前段的操作會使佇列變成下面這樣：
```c
["a", "b"]
```
但題目預期如下：
```c
["b"]
```
所以需要另外設立一個布林值來判斷當前節點是否與上一次迭代的字串相同，將布林值命名為 `is_dup`，每當找到重複字串的時候就設為 `true`，當目前迭代兩節點字串內容不相同，先判斷 `is_dup` 是否為 `true` 如果是就把當前 `entry` 刪除，如此一來就能達到題目預期。
#### 實作過程
一開始在實作的時候，一直遇到 segmentation fault，參考 [王彥傑](https://hackmd.io/@yanjiew/linux2023q1-lab0#q_delete_dup) 同學的程式才發現沒判斷 `entry` 指到最後一個節點及`safe` 指到 `head` 的情況。
```diff
...
- if (!strcmp(entry->value, safe->value)) {
+ if (&safe->list != head && !strcmp(entry->value, safe->value)) {
...
```
後來在考慮使用 `goto` 或是巨集來簡化，節點刪除並釋放的兩行操作。但最後由於，沒有減少幾行程式碼為由，不化簡重複的四行程式碼。
### q_swap
> Commit: [4ecc427](https://github.com/sysprog21/lab0-c/commit/4ecc4275b9e8c527ec2b06938c0e48c97da92eab)
#### 函式目標
交換佇列中鄰近的節點，詳見 [LeetCode 24. Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/)
#### 實作說明
一開始先檢查佇列是否為 NULL 或是空佇列。接著利用間接指標指向佇列頭部的下一個節點，需要交換的情形是要有兩個一組的節點，若在下次迭代只剩一個節點，就沒有交換的必要，因此每次迭代前要先確認間接指標指到的兩節節點的不是頭部。在迴圈中，利用 `list_move` 將間接指標所指向的節點移動到間接指標所指向的節點的下一個節點後方，達到交換相鄰節點的目的。
#### 實作過程
一開始，我是直接使用指標的操作，但後來覺得程式碼難以理解，因此去 `<list.h>` 看有沒有適合的函式能使用，就找到 `list_move` 來用於實作上。
### q_reverse
> Commit: [5a3e32e](https://github.com/sysprog21/lab0-c/commit/5a3e32efda2360b845b63e26dcf71809afb95feb)
#### 函式目標
以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點
#### 實作說明
首先，先檢查佇列是否為 NULL 或是空佇列。接著利用 `list_for_each_safe` 來迭代整個佇列，之後利用 `list_move` 函式將每個節點都移動到佇列頭部，進而達到以反向順序重新排列鏈結串列的效果。
#### 實作過程
原本想直接將佇列頭部指向的下一個節點指向最後一個節點，但在經過嘗試後發現好像行不通，所以採用實作說明的這種方法來實作。
### q_reverseK
> Commit: [b5a3bf8](https://github.com/sysprog21/lab0-c/commit/b5a3bf8f85b7cba331cb7bca42ea14539bf7bbb0)
#### 函式目標
類似 q_reverse，但指定每 k 個節點為一組，進行反向順序排列，詳見 [LeetCode 25. Reverse Nodes in k-Group](https://leetcode.com/problems/reverse-nodes-in-k-group/)
#### 實作說明
首先，先檢查佇列是否為 NULL 或是空佇列。接著利用 list_for_each_safe 來迭代節點。之後利用一個計數器來計算要一次將幾個節點進行反轉，大致流程為創建新的 list (tmp) 之後，將前 k 個節點切到 tmp 裡，之後利用 q_reverse 來進行反向排序。最後再將 tmp 裡的節點接回去原本的佇列裡，完成操作。
#### 實作過程
在實作過程中有參考 [rota1001](https://hackmd.io/@rota1001/linux2025-homework1) 及 [yanjiew](https://hackmd.io/@yanjiew/linux2023q1-lab0#q_reverseK) 的實作。
### q_sort
> Commit: []()
#### 函式目標
以遞增順序來排序鏈結串列的節點，可參閱 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 得知實作手法
#### 實作說明
#### 實作過程
### q_ascend 及 q_descend
> Commit: []()
#### 函式目標
參閱 [LeetCode 2487. Remove Nodes From Linked List](https://leetcode.com/problems/remove-nodes-from-linked-list/)，注意節點間的順序
#### 實作說明
#### 實作過程
### q_merge
> Commit: []()
#### 函式目標
合併所有已排序的佇列，並合而為一個新的已排序佇列，詳見 [LeetCode 23. Merge k Sorted Lists](https://leetcode.com/problems/merge-k-sorted-lists/)
#### 實作說明
#### 實作過程
Sign in with Wallet
Connect another wallet