# 2020q3 Homework1 (quiz1)
contributed by <`chwchao`>

> [2020q3 第 1 週測驗題](https://hackmd.io/@sysprog/sysprog2020-quiz1)

###### tags: `sysprog2020`

## 測驗題目解析 & 說明

定義一不存在環狀結構 (circular) 的單向 linked list 結構如下：

typedef struct __node {                   
    int value;
    struct __node *next;
} node_t;

digraph linkedlist {
    node [shape="record"]
    rankdir=LR;
    elem1 [label="{<val> value|<next>}"];
    elem2 [label="{<val> value|<next>}"];
    
    elem1:next:a -> elem2 [tailclip=false arrowtail="dot" dir="both"];
}

### AA1 & AA2 解析

定義一函式 `add_entry` 用於新增節點至 linked list 尾端，並由開發者指定開頭指標，
要求補上 AA1 及 AA2 的正確內容。

digraph feature {
    nodesep=1.0
    node [shape="record"]
    rankdir=LR;
    elem1 [label="{<val> value|<next>}"];
    elem2 [label="{<val> value|<next>}"];
    elem3 [label="{<val> new_value|<next>}" color="blue"];
    head [shape="none"];
    mid [label="addr"];
    
    "head" -> mid;
    mid -> elem1;
    elem1:next:a -> elem2 [tailclip=false arrowtail="dot" dir="both"];
    elem2:next:a -> elem3 [color="blue" tailclip=false arrowtail="dot" dir="both"];
}

void add_entry(node_t **head, int new_value)
{
    node_t **indirect = head;

    node_t *new_node = malloc(sizeof(node_t));
    new_node->value = new_value;
    new_node->next = NULL;

    AA1;
    while (*indirect)
        indirect = &(*indirect)->next;
    AA2;
}

#### 程式內容分析 & 解題思路

* 宣告一指標變數 `indirect` 指向 List 開頭指標儲存位址 (pointer of pointer)

> 為在移動指針至尾部的過程中，避免覆蓋參考指標 `head` 的原始值 (Memory Leak)

    node_t **indirect = head;

digraph step1 {
    nodesep=1.0
    node [shape="record"]
    rankdir=LR;
    elem1 [label="{<val> value|<next>}"];
    elem2 [label="{<val> value|<next>}"];
    head [shape="none"];
    indirect [shape="none"]
    mid [label="addr"];
    
    head -> mid;
    indirect -> mid [color="blue"];
    mid -> elem1;
    elem1:next:a -> elem2 [tailclip=false arrowtail="dot" dir="both"];
}

* 使用 malloc 分配一空間給新節點，並對其值進行初始化

> 該新節點後方須為空（尾部），即 new_node->next = NULL
> 此處 `new_node` 變數為該空間的記憶體位址（指標）

    node_t *new_node = malloc(sizeof(node_t));
    new_node->value = new_value;
    new_node->next = NULL;

digraph step2 {
    node [shape="record"]
    rankdir=LR;
    elem1 [label="{<val> value|<next>}"];
    elem2 [label="{<val> value|<next>}"];
    elem3 [label="{<val> new_value|<next>}" color="blue"];
    head [shape="none"];
    indirect [shape="none"]
    new_node [shape="none"]
    mid [label="addr"];
    
    head -> mid;
    indirect -> mid;
    mid -> elem1;
    elem1:next:a -> elem2 [tailclip=false arrowtail="dot" dir="both"];
    new_node -> elem3 [color="blue"];
    
    {rank=same; elem2; elem3}
}

* AA1
`(a) assert(new_node)`
`(b) *indirect = new_node`

可注意在 AA1 執行階段開始時，`indirect` 仍為 linked list 開頭， 若執行 (b)，即把 `*indirect` 值用新節點位址取代，等同將該節點後方內容移除，並以新節點取代 (如以下示意圖)。由於不符合程式需求，因此本處我們可以推論**解答應為 (a)，使用 `assert` 函式對 malloc 的執行結果做檢查**。

*於 AA1 執行 (b) 的結果：*

digraph wrong {
    node [shape="record"]
    rankdir=LR;
    elem1 [label="{<val> value|<next>}"];
    elem2 [label="{<val> value|<next>}"];
    elem3 [label="{<val> new_value|<next>}"];
    head [shape="none"];
    indirect [shape="none"]
    mid [label="new_node" color="blue"];
    
    head -> mid;
    indirect -> mid;
    mid -> elem3;
    elem1:next:a -> elem2 [tailclip=false arrowtail="dot" dir="both"];
    
    {rank=same; elem1; elem3}
}

* 移動 `indirect` 指針至 linked list 尾端

> 迴圈本體持續更新 `indirect` 至下一節點位址的儲存位址，直至 `*indirect` 為 NULL
>
> 可注意迴圈判斷式中 `*indirect` 為一節點空間的位址值，若其值為 NULL，代表 linked list 後方已無節點，而當前 `indirect` 指向之位址即為需存放新節點位址的空間。

    while (*indirect)
        indirect = &(*indirect)->next;

digraph step3_1 {
    node [shape="record"]
    rankdir=LR;
    elem1 [label="{<val> value|<next>}"];
    elem2 [label="{<val> value|<next>}"];
    head [shape="none"];
    mid [label="addr"];
    indirect [shape="none"]
    
    head -> mid;
    indirect -> elem1:next [color="blue"];
    mid -> elem1;
    elem1:next:a -> elem2 [tailclip=false arrowtail="dot" dir="both"];
}

digraph step3_2 {
    node [shape="record"]
    rankdir=LR;
    elem1 [label="{<val> value|<next>}"];
    elem2 [label="{<val> value|<next>}"];
    head [shape="none"];
    mid [label="addr"];
    indirect [shape="none"]
    
    head -> mid;
    indirect -> elem2:next [color="blue"];
    mid -> elem1;
    elem1:next:a -> elem2 [tailclip=false arrowtail="dot" dir="both"];
}

* AA2
`(a) assert(new_node)`
`(b) *indirect = new_node`

AA2 的部分，由於此處 `indirect` 已確定為新節點位址的儲存空間，因此**選 (b) 將新節點接至原 linked list 後方，以完成函式功能**。

digraph step2 {
    node [shape="record"]
    rankdir=LR;
    elem1 [label="{<val> value|<next>}"];
    elem2 [label="{<val> value|<next> new_node}" color="blue"];
    elem3 [label="{<val> new_value|<next>}"];
    head [shape="none"];
    indirect [shape="none"]
    mid [label="addr"];
    
    head -> mid;
    indirect -> elem2:next;
    mid -> elem1;
    elem1:next:a -> elem2 [tailclip=false arrowtail="dot" dir="both"];
    elem2:next -> elem3 [color="blue"];
}

### BB1 & BB2 解析

定義一函式 `swap_pair` 可將一 linked list 中節點成對交換，
要求補上 BB1 及 BB2 正確內容。

*Before :*

digraph feature {
    node [shape="record"]
    rankdir=LR;
    elem1 [label="{<val> value1|<next>}"];
    elem2 [label="{<val> value2|<next>}"];
    elem3 [label="{<val> value3|<next>}"];
    elem4 [label="{<val> value4|<next>}"];
    head [shape="none"];
    
    head -> elem1;
    elem1:next:a -> elem2 [tailclip=false arrowtail="dot" dir="both"];
    elem2:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both"];
    elem3:next:a -> elem4 [tailclip=false arrowtail="dot" dir="both"];
}

*After :*

digraph feature {
    node [shape="record"]
    rankdir=LR;
    elem1 [label="{<val> value2|<next>}" color="blue"];
    elem2 [label="{<val> value1|<next>}" color="blue"];
    elem3 [label="{<val> value4|<next>}" color="red"];
    elem4 [label="{<val> value3|<next>}" color="red"];
    head [shape="none"];
    
    head -> elem1;
    elem1:next:a -> elem2 [tailclip=false arrowtail="dot" dir="both"];
    elem2:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both"];
    elem3:next:a -> elem4 [tailclip=false arrowtail="dot" dir="both"];
}

node_t *swap_pair(node_t *head)
{
    for (node_t **node = &head; *node && (*node)->next; BB1) {
        node_t *tmp = *node;
        BB2;
        tmp->next = (*node)->next;
        (*node)->next = tmp;
    }
    return head;
}

#### 程式內容分析 & 解題思路

* 宣告一指標變數 `node` 指向開頭指標 `head` 的儲存位址，
以判斷該節點及下一節點是否均存在作為條件執行迴圈 (確認執行時均具成對節點)，
並在每次迴圈執行 BB1 之內容

    for (node_t **node = &head; *node && (*node)->next; BB1) {

digraph feature {
    node [shape="record"]
    rankdir=LR;
    elem1 [label="{<val> value1|<next>}"];
    elem2 [label="{<val> value2|<next>}"];
    elem3 [label="{<val> value3|<next>}"];
    elem4 [label="{<val> value4|<next>}"];
    head [shape="box" color="blue"];
    "node" [shape="none"];
    
    "node" -> head [color="blue"];
    head -> elem1;
    elem1:next:a -> elem2 [tailclip=false arrowtail="dot" dir="both"];
    elem2:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both"];
    elem3:next:a -> elem4 [tailclip=false arrowtail="dot" dir="both"];
}

* 根據函式功能，即兩兩交換一 linked list 中的節點，此處推論單一迴圈執行內容應為交換當前目標節點及下一節點。
>P.S.
>由程式中 *line 4* 首先宣告一區域變數 `tmp` 記錄原資訊，接著最後再將其存入另一變數，即此處的 `(*node)->next`，根據經驗亦可推測是執行交換動作）

因此先假設此處進行兩相鄰節點交換，推測程式內容：

* 使用一區域指標變數 `tmp` 指向當前目標節點

            node_t *tmp = *node;

    digraph feature {
        node [shape="record"]
        rankdir=LR;
        elem1 [label="{<val> value1|<next>}"];
        elem2 [label="{<val> value2|<next>}"];
        elem3 [label="{<val> value3|<next>}"];
        elem4 [label="{<val> value4|<next>}"];
        head [shape="box"];
        tmp [shape="none" color="blue"];
        "node" [shape="none"];

        "node" -> head ;
        head -> elem1;
        tmp -> elem1 [color="blue"];
        elem1:next:a -> elem2 [tailclip=false arrowtail="dot" dir="both"];
        elem2:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both"];
        elem3:next:a -> elem4 [tailclip=false arrowtail="dot" dir="both"];
    }

* BB2
`(a)` `node = (*node)->next`
`(b)` `node = &(*node)->next`
`(c)` `*node = (*node)->next`
`(d)` `*node = &(*node)->next`
`(e)` `*node = &((*node)->next)`

在根據題意選擇選項前，我們可以先判斷這五個選項等號左右側型別來進行刪去法：
`(a)` `node_t**` vs `node_t*`
`(b)` `node_t**` vs `node_t**`
`(c)` `node_t*` vs `node_t*`
`(d)` `node_t*` vs `node_t**`
`(e)` `node_t*` vs `node_t**`

以上可刪去除了 `(b)`、`(c)` 外的選項，且可發現 `(b)`、`(c)` 選項差別在於更改的為 `node` 或 `head` 的值，又根據函式最後一行 `return head`，可知道此函式需回傳新 linked list 的開頭，即第二節點，因此此處選擇**執行 `(c)`，將 `head` 指標更改為第二節點的位址**。

    digraph feature {
        node [shape="record"]
        rankdir=LR;
        elem1 [label="{<val> value1|<next>}"];
        elem2 [label="{<val> value2|<next>}"];
        elem3 [label="{<val> value3|<next>}"];
        elem4 [label="{<val> value4|<next>}"];
        head [shape="box"];
        tmp [shape="none"];
        "node" [shape="none"];

        "node" -> head;
        head -> elem2 [color="blue"];
        tmp -> elem1 ;
        elem1:next:a -> elem2 [tailclip=false arrowtail="dot" dir="both"];
        elem2:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both"];
        elem3:next:a -> elem4 [tailclip=false arrowtail="dot" dir="both"];
    }

* 把第二節點 (`node`) 尾部，即第三節點，接至第一節點 (`tmp`) 後方

            tmp->next = (*node)->next;

    digraph feature {
        node [shape="record"]
        rankdir=LR;
        elem1 [label="{<val> value1|<next>}"];
        elem2 [label="{<val> value2|<next>}"];
        elem3 [label="{<val> value3|<next>}"];
        elem4 [label="{<val> value4|<next>}"];
        head [shape="box"];
        tmp [shape="none"];
        "node" [shape="none"];

        "node" -> head;
        head -> elem2;
        tmp -> elem1 ;
        elem1:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both" color="blue"];
        elem2:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both"];
        elem3:next:a -> elem4 [tailclip=false arrowtail="dot" dir="both"];
    }

* 把第一節點 (`tmp`)，接至第二節點 (`node`) 後方

            (*node)->next = tmp;

    digraph feature {
        node [shape="record"]
        rankdir=LR;
        elem1 [label="{<val> value1|<next>}"];
        elem2 [labe="{<val> value2|<next>}"];
        elem3 [label="{<val> value3|<next>}"];
        elem4 [label="{<val> value4|<next>}"];
        head [shape="box"];
        tmp [shape="none"];
        "node" [shape="none"];

        "node" -> head;
        head -> elem2;
        tmp -> elem1 ;
        elem1:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both"];
        elem2:next:a -> elem1 [tailclip=false arrowtail="dot" dir="both" color="blue"];
        elem3:next:a -> elem4 [tailclip=false arrowtail="dot" dir="both"];
    }

* BB1
`(a)` `node = (*node)->next->next`
`(b)` `*node = (*node)->next->next`
`(c)` `*node = ((*node)->next)->next`
`(d)` `*node = &((*node)->next)->next`
`(e)` `node = &(*node)->next->next`
`(f)` `*node = &(*node)->next->next`

接著第一次迴圈結束，需執行 BB1 內容，此處發現單次迴圈會完成兩個節點的交換，因此可知道每次迴圈結束後須將新目標節點設為下一組的第一節點，即往後跳兩個節點。
但首先還是先進行型別比對：

`(a)` `node_t**` vs `node_t*`
`(b)` `node_t*` vs `node_t*`
`(c)` `node_t*` vs `node_t*`
`(d)` `node_t*` vs `node_t**`
`(e)` `node_t**` vs `node_t**`
`(f)` `node_t*` vs `node_t**`

以上可刪去除了 `(b)`、`(c)`、`(e)` 外的選項，考慮此時應已將 `head` 更改為正確內容，不應再做更動，若此處選擇 `(b)` 或 `(c)` 將再次覆蓋其值，因此此處**選擇 `(e)`，將 `node` 指向下兩個節點位址的儲存位址**。

    digraph feature {
        node [shape="record"]
        rankdir=LR;
        elem1 [label="{<val> value1|<next>}"];
        elem2 [label="{<val> value2|<next>}"];
        elem3 [label="{<val> value3|<next>}"];
        elem4 [label="{<val> value4|<next>}"];
        head [shape="box"];
        "node" [shape="none"];

        "node" -> elem1:next [color="blue"];
        head -> elem2;
        elem1:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both"];
        elem2:next:a -> elem1 [tailclip=false arrowtail="dot" dir="both"];
        elem3:next:a -> elem4 [tailclip=false arrowtail="dot" dir="both"];
    }

* 接著持續執行迴圈內容
* `tmp` 儲存當前目標節點位址

    digraph feature {
        node [shape="record"]
        rankdir=LR;
        elem1 [label="{<val> value1|<next>}"];
        elem2 [label="{<val> value2|<next>}"];
        elem3 [label="{<val> value3|<next>}"];
        elem4 [label="{<val> value4|<next>}"];
        head [shape="box"];
        "node" [shape="none"];
        tmp [shape="none"]

        "node" -> elem1:next;
        tmp -> elem3 [color="blue"];
        head -> elem2;
        elem1:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both"];
        elem2:next:a -> elem1 [tailclip=false arrowtail="dot" dir="both"];
        elem3:next:a -> elem4 [tailclip=false arrowtail="dot" dir="both"];
    }

* 將 `node` 指向之值改為第二節點位址

    digraph feature {
        node [shape="record"]
        rankdir=LR;
        elem1 [label="{<val> value1|<next>}"];
        elem2 [label="{<val> value2|<next>}"];
        elem3 [label="{<val> value3|<next>}"];
        elem4 [label="{<val> value4|<next>}"];
        head [shape="box"];
        "node" [shape="none"];
        tmp [shape="none"]

        "node" -> elem1:next;
        tmp -> elem3;
        head -> elem2;
        elem1:next:a -> elem4 [tailclip=false arrowtail="dot" dir="both" color="blue"];
        elem2:next:a -> elem1 [tailclip=false arrowtail="dot" dir="both"];
        elem3:next:a -> elem4 [tailclip=false arrowtail="dot" dir="both"];
    }

* 第三節點接回第一節點後方(此處為空)

    digraph feature {
        node [shape="record"]
        rankdir=LR;
        elem1 [label="{<val> value1|<next>}"];
        elem2 [label="{<val> value2|<next>}"];
        elem3 [label="{<val> value3|<next>}"];
        elem4 [label="{<val> value4|<next>}"];
        head [shape="box"];
        "node" [shape="none"];
        tmp [shape="none"]

        "node" -> elem1:next;
        tmp -> elem3;
        head -> elem2;
        elem1:next:a -> elem4 [tailclip=false arrowtail="dot" dir="both" color="blue"];
        elem2:next:a -> elem1 [tailclip=false arrowtail="dot" dir="both"];
    }

* 第一節點接至第二節點後方

    digraph feature {
        node [shape="record"]
        rankdir=LR;
        elem1 [label="{<val> value1|<next>}"];
        elem2 [label="{<val> value2|<next>}"];
        elem3 [label="{<val> value3|<next>}"];
        elem4 [label="{<val> value4|<next>}"];
        head [shape="box"];
        "node" [shape="none"];
        tmp [shape="none"]

        "node" -> elem1:next;
        tmp -> elem3;
        head -> elem2;
        elem1:next:a -> elem4 [tailclip=false arrowtail="dot" dir="both"];
        elem2:next:a -> elem1 [tailclip=false arrowtail="dot" dir="both"];
        elem4:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both" color="blue"];
    }

* 移動 `node` 指向下兩節點位址儲存位址

    digraph feature {
        node [shape="record"]
        rankdir=LR;
        elem1 [label="{<val> value1|<next>}"];
        elem2 [label="{<val> value2|<next>}"];
        elem3 [label="{<val> value3|<next>}"];
        elem4 [label="{<val> value4|<next>}"];
        head [shape="box"];
        "node" [shape="none"];

        "node" -> elem3:next [color="blue"];
        head -> elem2;
        elem1:next:a -> elem4 [tailclip=false arrowtail="dot" dir="both"];
        elem2:next:a -> elem1 [tailclip=false arrowtail="dot" dir="both"];
        elem4:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both"];
    }

* `*node` 為 NULL，結束迴圈並完成函式功能

### CCC 解析
定義一函式 `reverse` 可將一 linked list 中節點反向排列，
要求補上 CCC 正確內容。

*Before :*

digraph feature {
    node [shape="record"]
    rankdir=LR;
    elem1 [label="{<val> value1|<next>}"];
    elem2 [label="{<val> value2|<next>}"];
    elem3 [label="{<val> value3|<next>}"];
    head [shape="none"];
    
    head -> elem1;
    elem1:next:a -> elem2 [tailclip=false arrowtail="dot" dir="both"];
    elem2:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both"];
}

*After :*

digraph feature {
    node [shape="record"]
    rankdir=LR;
    elem1 [label="{<val> value1|<next>}"];
    elem2 [label="{<val> value2|<next>}"];
    elem3 [label="{<val> value3|<next>}"];
    head [shape="none"];
    
    head -> elem3;
    elem3:next:a -> elem2 [tailclip=false arrowtail="dot" dir="both"];
    elem2:next:a -> elem1 [tailclip=false arrowtail="dot" dir="both"];
}

node_t *reverse(node_t *head)
{
    node_t *cursor = NULL;
    while (head) {
        node_t *next = head->next;
        CCC;
        head = next;
    }
    return cursor;
}

#### 程式內容分析 & 解題思路

* 宣告一節點指標變數 `cursor` 並初始化為 NULL
* 執行一迴圈，以 `head` 變數非 NULL 作為判斷條件
* 迴圈中以一區域指標變數 `next` 紀錄 `head` 節點的下一節點

digraph feature {
    node [shape="record"]
    rankdir=LR;
    elem1 [label="{<val> value1|<next>}"];
    elem2 [label="{<val> value2|<next>}"];
    elem3 [label="{<val> value3|<next>}"];
    head [shape="none"];
    next [shape="none"]
    
    head -> elem1;
    next -> elem2
    elem1:next:a -> elem2 [tailclip=false arrowtail="dot" dir="both"];
    elem2:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both"];
}

* CCC
`(a)` `cursor = head; head->next = cursor`
`(b)` `head->next = cursor; cursor = head`
`(c)` `cursor = head`
`(d)` `head->next = cursor`
`(e)` `head->next->next = cursor; cursor->next = head`
`(f)` `cursor->next = head; head->next->next = cursor`

根據 `next = head->next` 及 `head = next`，可知道 `head` 指標將遍歷此 linked list 單方向由頭至尾，推測此程式應是以對調兩兩節點方向的方式進行反轉。
整理此處應做的事：
1. 將 `head` 節點指向 `cursor` (NULL for first time)
2. 用 `cursor` 儲存 `head` 節點以利下一次迴圈使用

因此**應選 `(b)`**。

流程如下：

* `head` 節點指向`cursor` （第一次為 NULL)

    digraph feature {
        node [shape="record"]
        rankdir=LR;
        elem1 [label="{<val> value1|<next>}"];
        elem2 [label="{<val> value2|<next>}"];
        elem3 [label="{<val> value3|<next>}"];
        head [shape="none"];
        next [shape="none"]

        head -> elem1;
        next -> elem2;
        elem2:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both"];
    }

* `cursor` 指向`head` 節點

    digraph feature {
        node [shape="record"]
        rankdir=LR;
        elem1 [label="{<val> value1|<next>}"];
        elem2 [label="{<val> value2|<next>}"];
        elem3 [label="{<val> value3|<next>}"];
        head [shape="none"];
        next [shape="none"];
        cursor [shape="none"];

        head -> elem1;
        next -> elem2;
        cursor -> elem1
        elem2:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both"];
    }

* `head` 指向`next` 節點

    digraph feature {
        node [shape="record"]
        rankdir=LR;
        elem1 [label="{<val> value1|<next>}"];
        elem2 [label="{<val> value2|<next>}"];
        elem3 [label="{<val> value3|<next>}"];
        head [shape="none"];
        next [shape="none"];
        cursor [shape="none"];

        head -> elem2;
        next -> elem2;
        cursor -> elem1;
        elem2:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both"];
    }

* 重複以上四動作直至 `head == NULL`

    digraph feature {
        node [shape="record"]
        rankdir=LR;
        elem1 [label="{<val> value1|<next>}"];
        elem2 [label="{<val> value2|<next>}"];
        elem3 [label="{<val> value3|<next>}"];
        head [shape="none"];
        next [shape="none"];
        cursor [shape="none"];

        head -> elem3;
        next -> elem3;
        cursor -> elem2;
        elem2:next:a -> elem1 [tailclip=false arrowtail="dot" dir="both"];
    }

    digraph feature {
        node [shape="record"]
        rankdir=LR;
        elem1 [label="{<val> value1|<next>}"];
        elem2 [label="{<val> value2|<next>}"];
        elem3 [label="{<val> value3|<next>}"];
        cursor [shape="none"];

        cursor -> elem3;
        elem2:next:a -> elem1 [tailclip=false arrowtail="dot" dir="both"];
        elem3:next:a -> elem2 [tailclip=false arrowtail="dot" dir="both"];
    }

* 此時可發現 `cursor` 指向新 linked list 的開頭，因此回傳值完成函式功能

## 延伸問題

### Q1: 解釋程式運作原理

#### `add_entry`
請見上方 [AA1 & AA2 解析](#AA1-amp-AA2-解析)

#### `swap_pair`
請見上方 [BB1 & BB2 解析](#BB1-amp-BB2-解析)

#### `reverse`
請見上方 [CCC 解析](#CCC-解析)

#### `find_entry`
定義一函式 `find_entry`，可在一 linked list 中搜尋內容符合輸入值 value 的節點並回傳其位址，否則回傳 NULL。

node_t *find_entry(node_t *head, int value)
{
    node_t *current = head;
    for (; current && current->value != value; current = current->next)
        /* interate */;
    return current;
}

預設一 linked list 如下，並欲搜尋值 value2：

digraph feature {
    node [shape="record"]
    rankdir=LR;
    elem1 [label="{<val> value1|<next>}"];
    elem2 [label="{<val> value2|<next>}"];
    elem3 [label="{<val> value3|<next>}"];
    head [shape="none"];
    
    head -> elem1;
    elem1:next:a -> elem2 [tailclip=false arrowtail="dot" dir="both"];
    elem2:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both"];
}

* 首先以一指標變數 `current` 儲存開頭節點位址

    node_t *current = head;

digraph feature {
    node [shape="record"]
    rankdir=LR;
    elem1 [label="{<val> value1|<next>}"];
    elem2 [label="{<val> value2|<next>}"];
    elem3 [label="{<val> value3|<next>}"];
    head [shape="none"];
    current [shape="none"];
    
    head -> elem1;
    current -> elem1 [color="blue"];
    elem1:next:a -> elem2 [tailclip=false arrowtail="dot" dir="both"];
    elem2:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both"];
}

* 接著持續將 `current` 指標後移，直至
1. `current` 變為 NULL
2. `current` 節點內容與輸入參數 `value` 相等

    for (; current && current->value != value; current = current->next)
    /* interate */;

digraph feature {
    node [shape="record"]
    rankdir=LR;
    elem1 [label="{<val> value1|<next>}"];
    elem2 [label="{<val> value2|<next>}" color="blue"];
    elem3 [label="{<val> value3|<next>}"];
    head [shape="none"];
    current [shape="none"];
    
    head -> elem1;
    current -> elem2 [color="blue"];
    elem1:next:a -> elem2 [tailclip=false arrowtail="dot" dir="both"];
    elem2:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both"];
}

* 當找到目標後，`current` 將保持指向該目標節點，並回傳位址以完成函式功能。
* 但若目標不存在此 linked list 中，`current` 指標終將等於最後一節點的 `next` 成員，即 NULL，此時亦會終止迴圈並回傳 NULL。

    return current;

#### `remove_entry`
定義一函式 `remove_entry`，可在一 linked list 中搜尋位址符合輸入參數 `entry` 的節點位址，及從 list 中移除並釋放該節點記憶體。

void remove_entry(node_t **head, node_t *entry)
{
    node_t **indirect = head;

    while ((*indirect) != entry)
        indirect = &(*indirect)->next;

    *indirect = entry->next;
    free(entry);
}

預設一 linked list 如下，並欲移除位於 addr2 的節點 (value2 之節點)：

digraph feature {
    node [shape="record"]
    rankdir=LR;
    elem1 [label="{<val> value1|<next>}"];
    elem2 [label="{<val> value2|<next>}"];
    elem3 [label="{<val> value3|<next>}"];
    head [shape="none"];
    
    head -> addr1;
    addr1 -> elem1
    elem1:next:a -> elem2 [tailclip=false arrowtail="dot" dir="both"];
    elem2:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both"];
}

* 首先已一指標變數 `indirect` 指向第一節點位址。

digraph feature {
    node [shape="record"]
    rankdir=LR;
    elem1 [label="{<val> value1|<next>}"];
    elem2 [label="{<val> value2|<next>}"];
    elem3 [label="{<val> value3|<next>}"];
    head [shape="none"];
    indirect [shape="none"];
    
    head -> addr1;
    indirect -> addr1 [color="blue"];
    addr1 -> elem1
    elem1:next:a -> elem2 [tailclip=false arrowtail="dot" dir="both"];
    elem2:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both"];
}

* 接著以一迴圈，當 `indirect` 指向之位址並非目標位址時，持續指向下一節點位址，若位址相同，則終止迴圈。

digraph feature {
    node [shape="record"]
    rankdir=LR;
    elem1 [label="{<val> value1|<next>}"];
    elem2 [label="{<val> value2|<next>}" color="blue"];
    elem3 [label="{<val> value3|<next>}"];
    head [shape="none"];
    indirect [shape="none"];
    
    head -> addr1;
    indirect -> elem1:next [color="blue"];
    addr1 -> elem1
    elem1:next:a -> elem2 [tailclip=false arrowtail="dot" dir="both" color="blue"];
    elem2:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both"];
}

* 接著將目標節點之下一節點位址儲存至當前 `indirect` 位址記憶體上。

digraph feature {
    node [shape="record"]
    rankdir=LR;
    elem1 [label="{<val> value1|<next>}"];
    elem2 [label="{<val> value2|<next>}"];
    elem3 [label="{<val> value3|<next>}"];
    head [shape="none"];
    indirect [shape="none"];
    
    head -> addr1;
    indirect -> elem1:next;
    addr1 -> elem1
    elem1:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both" color="blue"];
    elem2:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both"];
}

* 最後利用函式 `free(entry)` 釋放目標節點位址的物件內容，完成移除節點。

digraph feature {
    node [shape="record"]
    rankdir=LR;
    elem1 [label="{<val> value1|<next>}"];
    elem3 [label="{<val> value3|<next>}"];
    head [shape="none"];
    indirect [shape="none"];
    
    head -> addr1;
    indirect -> elem1:next;
    addr1 -> elem1
    elem1:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both" color="blue"];
}

#### `print_list`
定義一函式 `print_list`，可依序輸出一 linked list 所有節點內容 (`value`)。

void print_list(node_t *head)
{
    for (node_t *current = head; current; current = current->next)
        printf("%d ", current->value);
    printf("\n");
}

預設一 linked list 如下，並欲依序輸出其所有內容：

digraph feature {
    node [shape="record"]
    rankdir=LR;
    elem1 [label="{<val> value1|<next>}"];
    elem2 [label="{<val> value2|<next>}"];
    elem3 [label="{<val> value3|<next>}"];
    head [shape="none"];

    head -> elem1
    elem1:next:a -> elem2 [tailclip=false arrowtail="dot" dir="both"];
    elem2:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both"];
}

* 首先以一變數 `current` 指向第一節點

digraph feature {
    node [shape="record"]
    rankdir=LR;
    elem1 [label="{<val> value1|<next>}"];
    elem2 [label="{<val> value2|<next>}"];
    elem3 [label="{<val> value3|<next>}"];
    head [shape="none"];
    current [shape="none"];

    head -> elem1;
    current -> elem1 [color="blue"];
    elem1:next:a -> elem2 [tailclip=false arrowtail="dot" dir="both"];
    elem2:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both"];
}

* 接著以 `current` 是否為 NULL 作為迴圈判斷條件。若通過，輸出當前節點的內容 `value1`。

value1

* 接著將 `current` 移至下一節點及輸出該節點內容，並重複此動作直至 `current` 值變為 NULL 時終止迴圈完成功能。

digraph feature {
    node [shape="record"]
    rankdir=LR;
    elem1 [label="{<val> value1|<next>}"];
    elem2 [label="{<val> value2|<next>}"];
    elem3 [label="{<val> value3|<next>}"];
    head [shape="none"];
    current [shape="none"];

    head -> elem1;
    current->elem2 [color="blue"];
    elem1:next:a -> elem2 [tailclip=false arrowtail="dot" dir="both"];
    elem2:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both"];
}

value1 value2

digraph feature {
    node [shape="record"]
    rankdir=LR;
    elem1 [label="{<val> value1|<next>}"];
    elem2 [label="{<val> value2|<next>}"];
    elem3 [label="{<val> value3|<next>}"];
    head [shape="none"];
    current [shape="none"];

    head -> elem1;
    current -> elem3 [color="blue"];
    elem1:next:a -> elem2 [tailclip=false arrowtail="dot" dir="both"];
    elem2:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both"];
}

value1 value2 value3

digraph feature {
    node [shape="record"]
    rankdir=LR;
    elem1 [label="{<val> value1|<next>}"];
    elem2 [label="{<val> value2|<next>}"];
    elem3 [label="{<val> value3|<next>}"];
    head [shape="none"];

    head -> elem1
    elem1:next:a -> elem2 [tailclip=false arrowtail="dot" dir="both"];
    elem2:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both"];
}

value1 value2 value3

### Q2: 改寫函式 `swap_pair` 和 `reverse`

#### `swap_pair`

原程式碼及其[解析](#BB1-amp-BB2-解析)：

node_t *swap_pair(node_t *head)
{
    for (node_t **node = &head; *node && (*node)->next; node = &(*node)->next->next) {
        node_t *tmp = *node;
        *node = (*node)->next;
        tmp->next = (*node)->next;
        (*node)->next = tmp;
    }
    return head;
}

改寫程式碼：

void swap_pair(node_t **head)
{
	for(node_t **node = head; *node && (*node)->next; node = &(*node)->next->next)
	{
		node_t *tmp = *node;
		*node = (*node)->next;
		tmp->next = (*node)->next;
		(*node)->next = tmp;
	}
	return;
}

Notes:

* 於函式參數設定，更改 `node_t*` 為 `node_t**` 型別，使程式內部能修改其 `node_t*` 值，而非如原版本回傳至外部再行賦值。
* 由於輸入參數型別改變，需重新調整函式內部相關程式碼。
* 重新確認 linked list 開頭是否如功能需求將第二節點位址存至 `*head` ，本函式無需再額外處理，因此完成改動。

#### `reverse`

原程式碼及其[解析](#BB1-amp-BB2-解析)：

node_t *reverse(node_t *head)
{
    node_t *cursor = NULL;
    while (head) {
        node_t *next = head->next;
        head->next = cursor; cursor = head;
        head = next;
    }
    return cursor;
}

改寫程式碼：

void reverse(node_t **head)
{
    node_t *cursor = NULL;
    while(*head)
    {
        node_t *next = (*head)->next;
        (*head)->next = cursor; cursor = *head;
        *head = next;
    }
    *head = cursor;
    return ;
}

Notes:

* 於函式參數設定，更改 `node_t*` 為 `node_t**` 型別，使程式內部能修改其 `node_t*` 值，而非如原版本回傳至外部再行賦值。
* 由於輸入參數型別改變，需重新調整函式內部相關程式碼。
* 可發現單純改動後會將 `*head` 值改為 NULL，因此在函式結尾再將其指向 `cursor`，即最後一節點，亦是新的 linked list 節點。

### Q3: 以遞迴改寫上述的 `reverse`

原程式碼及其[解析](#BB1-amp-BB2-解析)：

node_t *reverse(node_t *head)
{
    node_t *cursor = NULL;
    while (head) {
        node_t *next = head->next;
        head->next = cursor; cursor = head;
        head = next;
    }
    return cursor;
}

改寫程式碼：

node_t *rev_recursive_part(node_t *head)
{
    if(!head || !head->next) return head;
    node_t *new_head = rev_recursive_part(head->next);
    if(head->next) head->next->next = head;
    head->next = NULL;
    return new_head;
}

void rev_recursive(node_t **head)
{
    *head = rev_recursive_part(*head);
}

改寫程式流程說明：

* 預設一 linked list 如下，並欲將節點順序反轉：

digraph feature {
    node [shape="record"]
    rankdir=LR;
    elem1 [label="{<val> value1|<next>}"];
    elem2 [label="{<val> value2|<next>}"];
    elem3 [label="{<val> value3|<next>}"];
    elem4 [label="{<val> value4|<next>}"];
    head [shape="none"];
    head_part [shape="none"];
    
    head -> addr1;
    addr1 -> elem1;
    head_part -> elem1;
    elem1:next:a -> elem2 [tailclip=false arrowtail="dot" dir="both"];
    elem2:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both"];
    elem3:next:a -> elem4 [tailclip=false arrowtail="dot" dir="both"];
}

* 首先藉 3~5 行，遞迴至 linked list 尾端，並回傳給倒數第二節點層，儲存最後節點位址至變數 `new_head`。

digraph feature {
    node [shape="record"]
    rankdir=LR;
    elem1 [label="{<val> value1|<next>}"];
    elem2 [label="{<val> value2|<next>}"];
    elem3 [label="{<val> value3|<next>}"];
    elem4 [label="{<val> value4|<next>}"];
    head [shape="none"];
    head_part [shape="none"];
    new_head [shape="none"]
    
    head -> addr1;
    addr1 -> elem1;
    head_part -> elem3 [color="blue"];
    new_head -> elem4 [color="blue"];
    elem1:next:a -> elem2 [tailclip=false arrowtail="dot" dir="both"];
    elem2:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both"];
    elem3:next:a -> elem4 [tailclip=false arrowtail="dot" dir="both"];
}

* 接著將當層節點之下一節點接至其前方，並將其 `next` 指標清空。

digraph feature {
    node [shape="record"]
    rankdir=LR;
    elem1 [label="{<val> value1|<next>}"];
    elem2 [label="{<val> value2|<next>}"];
    elem3 [label="{<val> value3|<next>}"];
    elem4 [label="{<val> value4|<next>}"];
    head [shape="none"];
    head_part [shape="none"];
    new_head [shape="none"]
    
    head -> addr1;
    addr1 -> elem1;
    head_part -> elem3;
    new_head -> elem4;
    elem1:next:a -> elem2 [tailclip=false arrowtail="dot" dir="both"];
    elem2:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both"];
    elem4:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both" color="blue"];
}

* 接著回傳 `new_node` 至上一層函式，可注意此處 `new_node` 值，即新的 linked list 開頭，將持續回傳至第一次 `rev_recursive_part` 呼叫，而過程中 的 `head` 參數則會由後至前遍歷 linked list 中各節點。

digraph feature {
    node [shape="record"]
    rankdir=LR;
    elem1 [label="{<val> value1|<next>}"];
    elem2 [label="{<val> value2|<next>}"];
    elem3 [label="{<val> value3|<next>}"];
    elem4 [label="{<val> value4|<next>}"];
    head [shape="none"];
    head_part [shape="none"];
    new_head [shape="none"];
    
    head -> addr1;
    addr1 -> elem1;
    head_part -> elem2 [color="blue"];
    new_head -> elem4;
    elem1:next:a -> elem2 [tailclip=false arrowtail="dot" dir="both"];
    elem2:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both"];
    elem4:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both"];
}

* 接著持續退出遞迴直至第一次呼叫

digraph feature {
    node [shape="record"]
    rankdir=LR;
    elem1 [label="{<val> value1|<next>}"];
    elem2 [label="{<val> value2|<next>}"];
    elem3 [label="{<val> value3|<next>}"];
    elem4 [label="{<val> value4|<next>}"];
    head [shape="none"];
    head_part [shape="none"];
    new_head [shape="none"]
    
    head -> addr1;
    addr1 -> elem1;
    head_part -> elem1 [color="blue"];
    new_head -> elem4;
    elem1:next:a -> elem2 [tailclip=false arrowtail="dot" dir="both"];
    elem3:next:a -> elem2 [tailclip=false arrowtail="dot" dir="both" color="blue"];
    elem4:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both"];
}

digraph feature {
    node [shape="record"]
    rankdir=LR;
    elem1 [label="{<val> value1|<next>}"];
    elem2 [label="{<val> value2|<next>}"];
    elem3 [label="{<val> value3|<next>}"];
    elem4 [label="{<val> value4|<next>}"];
    head [shape="none"];
    new_head [shape="none"]
    
    head -> addr1;
    addr1 -> elem1;
    new_head -> elem4;
    elem2:next:a -> elem1 [tailclip=false arrowtail="dot" dir="both" color="blue"];
    elem3:next:a -> elem2 [tailclip=false arrowtail="dot" dir="both"];
    elem4:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both"];
}

* 最後將回傳的 `new_head` 值存至 `*head`，完成 linked list 倒轉。

digraph feature {
    node [shape="record"]
    rankdir=LR;
    elem1 [label="{<val> value1|<next>}"];
    elem2 [label="{<val> value2|<next>}"];
    elem3 [label="{<val> value3|<next>}"];
    elem4 [label="{<val> value4|<next>}"];
    head [shape="none"];
    
    head -> new_head [color="blue"];
    new_head -> elem4;
    elem2:next:a -> elem1 [tailclip=false arrowtail="dot" dir="both"];
    elem3:next:a -> elem2 [tailclip=false arrowtail="dot" dir="both"];
    elem4:next:a -> elem3 [tailclip=false arrowtail="dot" dir="both"];
}

### Q4: 針對 singly-linked list 的節點，實作 Fisher–Yates shuffle

實作程式碼：

// Move kth node to the end of the linked list
void move_entry(node_t **head, int k)
{
    node_t **indirect = head;
    node_t *target = NULL;

    // Find the target node, if found, store & remove the node
    while(*indirect)
    {        
        k--;
        if(k == 0)
        {
            target = *indirect;
            *indirect = (*indirect)->next;
            target->next = NULL;
        }
        if(*indirect) indirect = &(*indirect)->next;
    }
    
    // Add node to end of the list
    *indirect = target;
    return;
}

// Get length of a list
int get_length(node_t *head)
{
    int len = 0;
    while(head)
    {
        len++;
        head = head->next;
    }
    return len;
}

// Fisher-Yates shuffle
void Fisher_Yates_shuffle(node_t **head)
{
    srand(time(NULL));
    for(int left = get_length(*head); left > 0; left--)
        move_entry(head, rand() % left + 1);
    return;
}

程式碼說明：

* **`move_entry`**

函式功能為將一串列之第 k 節點移動至最尾端。

考慮 Fisher-Yates Shuffle 將隨機節點儲存至一新串列尾部的原理，亦可用原串列尾部一定長度替代該新串列的手法實作，此法除可以降低複製至新串列過程所需額外記憶體用量，亦可省去分配及釋放記憶體時的時間成本，因此實作之。

本函式實作可視為題目提供原始碼 `add_entry` 及 `remove_entry` 之結合。

* **`get_length`**

函式功能為取得輸入串列之長度。由於需要決定隨機節點位置，必須先取得當前長度以方便用 `rand()` 實作隨機數取得，因此實作之。

* **`Fisher_Yates_shuffle`**

此為演算法本體，可將輸入串列以 Fisher-Yates shuffle 重新排序，產生一新隨機串列。

在迴圈起始時確認該串列長度，並以 `left` 變數的遞減，分割未處理串列及以排序新串列。迴圈中則產生一範圍在 [ 1, 未處理串列長度] 之隨機數，並將該節點移至新串列最後方。當 `left` 值為 0，即所有節點以重新安插至新串列中時，迴圈結束並完成排序。

:::danger
:warning: 程式碼縮排一律是 4 個空白
:notes: jserv
:::
:::info
瞭解了～之後會改一下寫程式的習慣
by chwchao
:::