# 2020q3 Homework1 (quiz1)

contributed by < `Uduru0522` >

###### tags: `perspective and application of computer systems 2020`
[TOC]

----

# 問題
:::info
考慮一 singly linked list , 其結構定義如下：
</br>

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

已知**不存在環狀結構**，請補完下方程式碼 AA1, AA2, BB1, BB2, CCC 之部分
:::spoiler 點此展開程式碼
**Source Code**

#include <stdio.h>
#include <stdlib.h>

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

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;
}

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

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

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

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

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_t *reverse(node_t *head)
{
    node_t *cursor = NULL;
    while (head) {
        node_t *next = head->next;
        CCC;
        head = next;
    }
    return cursor;
}

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

int main(int argc, char const *argv[])
{
    node_t *head = NULL;

    print_list(head);

    add_entry(&head, 72);
    add_entry(&head, 101);
    add_entry(&head, 108);
    add_entry(&head, 109);
    add_entry(&head, 110);
    add_entry(&head, 111);

    print_list(head);

    node_t *entry = find_entry(head, 101);
    remove_entry(&head, entry);

    entry = find_entry(head, 111);
    remove_entry(&head, entry);

    print_list(head);

    /* swap pair.
     * See https://leetcode.com/problems/swap-nodes-in-pairs/
     */
    head = swap_pair(head);
    print_list(head);

    head = reverse(head);
    print_list(head);

    return 0;
}

**Output**

72 101 108 109 110 111 
72 108 109 110 
108 72 110 109
109 110 72 108

:::

# 各函式分析
### `add_entry()`

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
    assert(new_node);
    while (*indirect)
        indirect = &(*indirect)->next;
    //AA2
    *indirect = new_node;
}

+ 函式首先嘗試取得一塊新的 `node_t` 大小的記憶體空間並初始化：

digraph structs{
    rankdir = LR
    node[shape = record]
    
    INDIRECT[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   indirect  "
        shape = plain
    ]
    HEAD[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   head  "
        shape = plain
    ]
    list_node_1[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node1|<f1>value}|<f2>next}"
    ]
    list_node_2[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node2|<f1>value}|<f2>next}"
    ]
    NULL_1[label = "NULL", shape = plain]
    NULL_2[label = "NULL", shape = plain]
    new_node[
        style = "filled"
        fillcolor = "lightblue1"
        label = "{{<f0>new_node|<f1>new_value}|<f2>next}"
    ]
    
    { rank = same; HEAD new_node}
    
    INDIRECT -> HEAD
    HEAD -> list_node_1
    list_node_1:f2 -> list_node_2
    list_node_2:f2 -> NULL_2
    new_node:f2 -> NULL_1
}

+ `assert()` 於 `<assert.h>` 之下。根據 assert(3):
:::warning
**If expression is false (i.e., compares equal to zero), `assert()` prints an error message to standard error and terminates the program by calling `abort()`.**
The error message includes the name of the file and function containing the `assert()` call, the source code line number of the call, and the text of the argument; something like:

prog: file_name.c:16: func_name: Assertion `val == 0' failed.
:::
搭配 `malloc()` , 根據 malloc(3):
> on error, these functions return `NULL`

可用來檢測記憶體區塊取得失敗的情形。
+ 再向前移動，尋找最後的 NULL pointer

digraph structs{
    rankdir = LR
    node[shape = record]
    
    INDIRECT[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   indirect  "
        shape = plain
    ]
    HEAD[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   head  "
        shape = plain
    ]
    list_node_1[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node1|<f1>value}|<f2>next}"
    ]
    list_node_2[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node2|<f1>value}|<f2>next}"
    ]
    NULL_1[label = "NULL", shape = plain]
    NULL_2[label = "NULL", shape = plain]
    new_node[
        style = "filled"
        fillcolor = "lightblue1"
        label = "{{<f0>new_node|<f1>new_value}|<f2>next}"
    ]
    
    { rank = "same" new_node HEAD }
    
    INDIRECT -> list_node_1:f2;
    HEAD -> list_node_1;
    list_node_1:f2 -> list_node_2;
    list_node_2:f2 -> NULL_2;
    new_node:f2 -> NULL_1
}

digraph structs{
    rankdir = LR
    node[shape = record]
    
    INDIRECT[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   indirect  "
        shape = plain
    ]
    HEAD[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   head  "
        shape = plain
    ]
    list_node_1[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node1|<f1>value}|<f2>next}"
    ]
    list_node_2[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node2|<f1>value}|<f2>next}"
    ]
    NULL_1[label = "NULL", shape = plain]
    NULL_2[label = "NULL", shape = plain]
    new_node[
        style = "filled"
        fillcolor = "lightblue1"
        label = "{{<f0>new_node|<f1>new_value}|<f2>next}"
    ]
    
    { rank = "same" new_node HEAD }
    
    INDIRECT -> list_node_2:f2;
    HEAD -> list_node_1;
    list_node_1:f2 -> list_node_2;
    list_node_2:f2 -> NULL_2;
    new_node:f2 -> NULL_1
}

+ 最後再將 `new_node` 接上最後尾

digraph structs{
    rankdir = LR
    node[shape = record]
    
    INDIRECT[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   indirect  "
        shape = plain
    ]
    HEAD[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   head  "
        shape = plain
    ]
    list_node_1[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node1|<f1>value}|<f2>next}"
    ]
    list_node_2[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node2|<f1>value}|<f2>next}"
    ]
    NULL_1[label = "NULL", shape = plain]
    new_node[
        style = "filled"
        fillcolor = "lightblue1"
        label = "{{<f0>new_node|<f1>new_value}|<f2>next}"
    ]
    
    { rank = "same" INDIRECT HEAD }

    INDIRECT -> list_node_2:f2
    HEAD -> list_node_1
    list_node_1:f2 -> list_node_2
    list_node_2:f2 -> new_node
    new_node:f2 -> NULL_1
}

### `remove_entry()`

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

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

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

+ 此實做需配合前方使用 `find_entry()` 取得欲刪除的節點之前一個節點的 `next`
+ 假設欲刪除 `node2` (因此 `entry` 等同於 `node.next`)

digraph structs{
    rankdir = LR
    node[shape = record]
    
    INDIRECT[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   indirect  "
        shape = plain
    ]
    HEAD[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   head  "
        shape = plain
    ]
    list_node_1[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node1|<f1>value}|<f2>next}"
    ]
    list_node_2[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node2|<f1>value}|<f2>next}"
    ]
    NULL[label = "NULL", shape = plain]
    
    INDIRECT -> HEAD
    HEAD -> list_node_1
    list_node_1:f2 -> list_node_2
    list_node_2:f2 -> NULL
}

+ 向前移動 `indirect` ，尋找 `entry`

digraph structs{
    rankdir = LR
    node[shape = record]
    
    INDIRECT[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   indirect  "
        shape = plain
    ]
    HEAD[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   head  "
        shape = plain
    ]
    list_node_1[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node1|<f1>value}|<f2>next}"
    ]
    list_node_2[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node2|<f1>value}|<f2>next}"
    ]
    NULL[label = "NULL", shape = plain]
    
    INDIRECT -> list_node_1:f2
    HEAD -> list_node_1
    list_node_1:f2 -> list_node_2
    list_node_2:f2 -> NULL
}

+ 找到之後直接將 `entry->next` 直接接上前方節點

digraph structs{
    rankdir = LR
    node[shape = record]
    
    INDIRECT[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   indirect  "
        shape = plain
    ]
    BLANK_1[
        style = "filled, rounded, invis"
        label = " "
        shape = plain
    ]
    BLANK_2[
        style = "filled, rounded, invis"
        label = " "
        shape = plain
    ]
    HEAD[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   head  "
        shape = plain
    ]
    ENTRY[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   entry  "
        shape = plain
    ]
    list_node_1[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node1|<f1>value}|<f2>next}"
    ]
    list_node_2[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node2|<f1>value}|<f2>next}"
    ]
    NULL[label = "    NULL  ", shape = plain]
    
    { rank = same; INDIRECT BLANK_1 HEAD BLANK_2 ENTRY}
    
    INDIRECT -> BLANK_1 -> HEAD -> BLANK_2 -> ENTRY[
        style = invis
    ]
    INDIRECT -> list_node_1:f2
    HEAD -> list_node_1
    list_node_1:f2 -> NULL
    list_node_2:f2 -> NULL
    ENTRY -> list_node_2
}

+ 最後將 `entry` 的記憶體釋放掉。

digraph structs{
    rankdir = LR
    node[shape = record]
    
    INDIRECT[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   indirect  "
        shape = plain
    ]
    HEAD[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   head  "
        shape = plain
    ]
    list_node_1[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{d<f0>node1|<f1>value}|<f2>next}"
    ]
    NULL[label = "    NULL  ", shape = plain]
    BLANK_1[
        label = " "
        shape = box
        style = invis
    ]
    BLANK_2[
        label = " "
        shape = box
        style = invis
    ]
    
    { rank = same; HEAD INDIRECT }
    
    INDIRECT -> HEAD[style = invis]
    BLANK_2 -> list_node_1[style = invis]
    INDIRECT -> HEAD[style = invis]
    INDIRECT -> list_node_1:f2
    HEAD -> list_node_1
    list_node_1:f2 -> NULL
}

### `swap_pair()`

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

+ 初始狀態：

digraph structs{
    rankdir = LR
    node[shape = record]
    
    NODE_[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   node  "
        shape = plain
    ]
    HEAD[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   head  "
        shape = plain
    ]
    list_node_1[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node1|<f1>value}|<f2>next}"
    ]
    list_node_2[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node2|<f1>value}|<f2>next}"
    ]
    list_node_3[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node3|<f1>value}|<f2>next}"
    ]
    list_node_4[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node4|<f1>value}|<f2>next}"
    ]
    NULL[label = "NULL", shape = plain]
    
    { rank = "same" NODE_ HEAD }
    
    NODE_ -> HEAD;
    HEAD -> list_node_1
    list_node_1:f2 -> list_node_2
    list_node_2:f2 -> list_node_3
    list_node_3:f2 -> list_node_4
    list_node_4:f2 -> NULL
}

+ 每次進入迴圈，創建一個與 `*node` 相同的暫時指標

digraph structs{
    rankdir = LR
    node[shape = record]
    
    NODE_[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   node  "
        shape = plain
    ]
    HEAD[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   head  "
        shape = plain
    ]
    TEMP[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   temp  "
        shape = plain
    ]
    list_node_1[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node1|<f1>value}|<f2>next}"
    ]
    list_node_2[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node2|<f1>value}|<f2>next}"
    ]
    list_node_3[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node3|<f1>value}|<f2>next}"
    ]
    list_node_4[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node4|<f1>value}|<f2>next}"
    ]
    NULL[label = "NULL", shape = plain]
    
    { rank = "same" NODE_ HEAD TEMP }
    
    NODE_ -> HEAD;
    HEAD -> TEMP[style = invis]
    HEAD -> list_node_1
    TEMP -> list_node_1
    list_node_1:f2 -> list_node_2
    list_node_2:f2 -> list_node_3
    list_node_3:f2 -> list_node_4
    list_node_4:f2 -> NULL
}

+ 先將 `*node` 向前移動

digraph structs{
    rankdir = LR
    node[shape = record]
    
    NODE_[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   node  "
        shape = plain
    ]
    HEAD[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   head  \n   (Same address as node1.next)   "
        shape = plain
    ]
    TEMP[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   temp  "
        shape = plain
    ]
    list_node_1[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node1|<f1>value}|<f2>next}"
    ]
    list_node_2[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node2|<f1>value}|<f2>next}"
    ]
    list_node_3[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node3|<f1>value}|<f2>next}"
    ]
    list_node_4[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node4|<f1>value}|<f2>next}"
    ]
    NULL[label = "NULL", shape = plain]
    
    { rank = "same" HEAD TEMP }
    
    NODE_ -> HEAD -> list_node_2
    TEMP -> list_node_1
    list_node_1:f2 -> list_node_2
    list_node_2:f2 -> list_node_3
    list_node_3:f2 -> list_node_4
    list_node_4:f2 -> NULL
}

+ 將 `*node` 目前指向的節點的前項之 `next` 指向後項

digraph structs{
    rankdir = LR
    node[shape = record]
    
    NODE_[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   node  "
        shape = plain
    ]
    HEAD[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   head  "
        shape = plain
    ]
    TEMP[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   temp  "
        shape = plain
    ]
    list_node_1[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node1|<f1>value}|<f2>next}"
    ]
    list_node_2[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node2|<f1>value}|<f2>next}"
    ]
    list_node_3[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node3|<f1>value}|<f2>next}"
    ]
    list_node_4[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node4|<f1>value}|<f2>next}"
    ]
    NULL[label = "NULL", shape = plain]
    
    { rank = "same" HEAD TEMP }
    
    NODE_ -> HEAD -> list_node_2
    TEMP -> list_node_1
    list_node_1:f2 -> list_node_3
    list_node_2:f2 -> list_node_3
    list_node_3:f2 -> list_node_4
    list_node_4:f2 -> NULL
}

+ 再將 `*node` 指向前項，**注意此時 `node_t *head` 也完成了位置的修正**

digraph structs{
    rankdir = LR
    node[shape = record]
    
    NODE_[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   node  "
        shape = plain
    ]
    HEAD[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   head  "
        shape = plain
    ]
    TEMP[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   temp  "
        shape = plain
    ]
    list_node_1[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node1|<f1>value}|<f2>next}"
    ]
    list_node_2[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node2|<f1>value}|<f2>next}"
    ]
    list_node_3[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node3|<f1>value}|<f2>next}"
    ]
    list_node_4[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node4|<f1>value}|<f2>next}"
    ]
    NULL[label = "NULL", shape = plain]
    
    { rank = "same" list_node_2 TEMP }
    
    NODE_ -> HEAD -> list_node_2
    TEMP -> list_node_1
    list_node_1:f2 -> list_node_3
    list_node_2:f2 -> list_node_1
    list_node_3:f2 -> list_node_4
    list_node_4:f2 -> NULL
}

+ 將 `node` 前進兩個節點，重複動作。此時 `head` 不會再被移動。

digraph structs{
    rankdir = LR
    node[shape = record]
    
    NODE_[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   node  "
        shape = plain
    ]
    HEAD[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   head  "
        shape = plain
    ]
    list_node_1[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node1|<f1>value}|<f2>next}"
    ]
    list_node_2[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node2|<f1>value}|<f2>next}"
    ]
    list_node_3[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node3|<f1>value}|<f2>next}"
    ]
    list_node_4[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node4|<f1>value}|<f2>next}"
    ]
    NULL[label = "NULL", shape = plain]
    
    { rank = "same" NODE_ list_node_2}
    
    HEAD -> list_node_2
    NODE_ -> list_node_1:f2
    list_node_1:f2 -> list_node_3
    list_node_2:f2 -> list_node_1
    list_node_3:f2 -> list_node_4
    list_node_4:f2 -> NULL
}

digraph structs{
    rankdir = LR
    node[shape = record]
    
    NODE_[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   node  "
        shape = plain
    ]
    HEAD[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   head  "
        shape = plain
    ]
    TEMP[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "temp\n    (Same as node1.next)   "
        shape = plain
    ]
    list_node_1[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node1|<f1>value}|<f2>next}"
    ]
    list_node_2[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node2|<f1>value}|<f2>next}"
    ]
    list_node_3[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node3|<f1>value}|<f2>next}"
    ]
    list_node_4[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node4|<f1>value}|<f2>next}"
    ]
    NULL[label = "NULL", shape = plain]
    
    { rank = "same" NODE_ list_node_2}
    
    HEAD -> list_node_2
    NODE_ -> list_node_1:f2
    TEMP -> list_node_3
    list_node_1:f2 -> list_node_3
    list_node_2:f2 -> list_node_1
    list_node_3:f2 -> list_node_4
    list_node_4:f2 -> NULL
}

digraph structs{
    rankdir = LR
    node[shape = record]
    
    NODE_[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   node  "
        shape = plain
    ]
    HEAD[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   head  "
        shape = plain
    ]
    TEMP[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "temp\n    (Same as node1.next)   "
        shape = plain
    ]
    list_node_1[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node1|<f1>value}|<f2>next}"
    ]
    list_node_2[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node2|<f1>value}|<f2>next}"
    ]
    list_node_3[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node3|<f1>value}|<f2>next}"
    ]
    list_node_4[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node4|<f1>value}|<f2>next}"
    ]
    NULL[label = "NULL", shape = plain]
    
    { rank = "same" NODE_ list_node_1}
    
    HEAD -> list_node_2
    NODE_ -> list_node_3:f2
    TEMP -> list_node_3
    list_node_1:f2 -> list_node_3
    list_node_2:f2 -> list_node_1
    list_node_3:f2 -> list_node_4
    list_node_4:f2 -> NULL
}

digraph structs{
    rankdir = LR
    node[shape = record]
    
    NODE_[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   node  "
        shape = plain
    ]
    HEAD[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   head  "
        shape = plain
    ]
    TEMP[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "temp\n    (Same as node1.next)   "
        shape = plain
    ]
    list_node_1[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node1|<f1>value}|<f2>next}"
    ]
    list_node_2[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node2|<f1>value}|<f2>next}"
    ]
    list_node_3[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node3|<f1>value}|<f2>next}"
    ]
    list_node_4[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node4|<f1>value}|<f2>next}"
    ]
    NULL[label = "NULL", shape = plain]
    
    { rank = "same" NODE_ list_node_1}
    
    HEAD -> list_node_2
    NODE_ -> list_node_3:f2
    TEMP -> list_node_4
    list_node_1:f2 -> list_node_4
    list_node_2:f2 -> list_node_1
    list_node_3:f2 -> NULL
    list_node_4:f2 -> NULL
}

digraph structs{
    rankdir = LR
    node[shape = record]
    
    NODE_[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   node  "
        shape = plain
    ]
    HEAD[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   head  "
        shape = plain
    ]
    TEMP[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "temp\n    (Same as node1.next)   "
        shape = plain
    ]
    list_node_1[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node1|<f1>value}|<f2>next}"
    ]
    list_node_2[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node2|<f1>value}|<f2>next}"
    ]
    list_node_3[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node3|<f1>value}|<f2>next}"
    ]
    list_node_4[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node4|<f1>value}|<f2>next}"
    ]
    NULL[label = "NULL", shape = plain]
    
    { rank = "same" TEMP list_node_1 }
    { rank = "same" NODE_ list_node_4 }
    
    HEAD -> list_node_2
    NODE_ -> list_node_3:f2
    TEMP -> list_node_4
    list_node_1:f2 -> list_node_4
    list_node_2:f2 -> list_node_1
    list_node_3:f2 -> NULL
    list_node_4:f2 -> list_node_3
}

### `reverse()`

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

+ 以 `cursor` 儲存**已處裡**的部分，`head` 指向**未處理**的部分。
+ 初始狀態

digraph structs{
    rankdir = LR
    node[shape = record]
    
    HEAD[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   head  "
        shape = plain
    ]
    CURSOR[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   cursor  "
        shape = plain
    ]
    list_node_1[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node1|<f1>value}|<f2>next}"
    ]
    list_node_2[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node2|<f1>value}|<f2>next}"
    ]
    NULL[label = "NULL", shape = plain]
    NULL_END[label = "NULL", shape = plain]
    
    HEAD -> list_node_1
    list_node_1:f2 -> list_node_2
    list_node_2:f2 -> NULL
    CURSOR -> NULL_END
}

+ 新增 `node_t *next`，為下次迴圈中要處理的節點

digraph structs{
    rankdir = LR
    node[shape = record]
    
    HEAD[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   head  "
        shape = plain
    ]
    CURSOR[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   cursor  "
        shape = plain
    ]
    NEXT[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   next  "
        shape = plain
    ]
    list_node_1[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node1|<f1>value}|<f2>next}"
    ]
    list_node_2[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node2|<f1>value}|<f2>next}"
    ]
    NULL[label = "NULL", shape = plain]
    NULL_END[label = "NULL", shape = plain]
    
    NEXT -> list_node_2
    HEAD -> list_node_1
    list_node_1:f2 -> list_node_2
    list_node_2:f2 -> NULL
    CURSOR -> NULL_END
}

+ 將head指向的節點接到 `cursor` 上

digraph structs{
    rankdir = LR
    node[shape = record]
    
    HEAD[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   head  "
        shape = plain
    ]
    CURSOR[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   cursor  "
        shape = plain
    ]
    NEXT[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   next  "
        shape = plain
    ]
    list_node_1[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node1|<f1>value}|<f2>next}"
    ]
    list_node_2[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node2|<f1>value}|<f2>next}"
    ]
    NULL[label = "NULL", shape = plain]
    NULL_END[label = "NULL", shape = plain]
    
    NEXT -> list_node_2
    HEAD -> list_node_1
    list_node_1:f2 -> NULL_END
    list_node_2:f2 -> NULL
    CURSOR -> NULL_END
}

+ 將 `cursor` 指向**已處理**部分的開頭

digraph structs{
    rankdir = LR
    node[shape = record]
    
    HEAD[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   head  "
        shape = plain
    ]
    CURSOR[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   cursor  "
        shape = plain
    ]
    NEXT[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   next  "
        shape = plain
    ]
    list_node_1[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node1|<f1>value}|<f2>next}"
    ]
    list_node_2[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node2|<f1>value}|<f2>next}"
    ]
    NULL[label = "NULL", shape = plain]
    NULL_END[label = "NULL", shape = plain]
    BLANK[shape = plain, label = " ", style = invis]
    
    { rank = same; CURSOR HEAD BLANK NEXT }
    
    CURSOR -> HEAD -> BLANK -> NEXT[style = invis]
    NEXT -> list_node_2
    HEAD -> list_node_1
    list_node_1:f2 -> NULL_END
    list_node_2:f2 -> NULL
    CURSOR -> list_node_1
}

+ 再將 `head` 指回**未處理**部分的開頭，重複迴圈直到 `head` 指向 `NULL`

digraph structs{
    rankdir = LR
    node[shape = record]
    
    HEAD[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   head  "
        shape = plain
    ]
    CURSOR[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   cursor  "
        shape = plain
    ]
    NEXT[
        style = "filled, rounded"
        fillcolor = "palegreen"
        label = "   next  "
        shape = plain
    ]
    list_node_1[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node1|<f1>value}|<f2>next}"
    ]
    list_node_2[
        style = "filled"
        fillcolor = "lightskyblue3"
        label = "{{<f0>node2|<f1>value}|<f2>next}"
    ]
    NULL[label = "NULL", shape = plain]
    NULL_END[label = "NULL", shape = plain]
    BLANK[shape = plain, label = " ", style = invis]
    
    { rank = same; CURSOR HEAD BLANK NEXT }
    
    CURSOR -> BLANK -> HEAD -> NEXT[style = invis]
    NEXT -> list_node_2
    HEAD -> list_node_2
    list_node_1:f2 -> NULL_END
    list_node_2:f2 -> NULL
    CURSOR -> list_node_1
}

### `find_entry()`

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

+ 使用 `for` 終止條件進行搜尋。
+ 判斷式 `current && current->value != value` 利用 `&&` 的 **short-circut evaluation** 特性，在 `current == NULL` 時不進行後方的取值動作。
:::warning
`&&` `||` `?` 三個 operator 有這項特性，若第一個 expression 已可以確定結果(例如 `false && X` 必為 `false`)，右方 expression 便不會被執行
:::
+ 回傳值若非 `NULL` ，必為上一個節點的 `next` 值，方便搭配 `remove_entry()` 使用

### `print_list()`

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

自 `head` 開始在 list 之中進行穿隧並逐一印出 `value` ，很直覺。

----

# 延伸問題
### Q1-1. 以 pointer-to-pointer 實做 `swap_pair()`。
由於原先的實做中的 `node_t **node` 單純只是複製一份 pointer-to-pointer , 我們可以在修正傳入參數之後，直接代換以達成效果。

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

### Q1-2 以 pointer-to-pointer 實做 `reverse()`。
同 Q1-1。
由於 `cursor` 會指向已倒序完成的 list , 最後將它接回 `head` 上。

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;
}

### Q2. 以遞迴方式實作 `reverse()`。
沿用原本的實作邏輯，但將 while 迴圈改成以遞迴的方式實現。
`done` 指向已處理的部分，`remain` 指向未處理的部分，每層迴圈將 `remain` 的第一個加進相反 `done` 裡。

node_t *reverse_recursive(node_t *remain, node_t *done){
    if (!remain){
        return done;
    }

    node_t *next = remain->next;
    remain->next = done;
    return reverse_recursive(next, remain);
}

void reverse(node_t **head){
    *head = reverse_recursive(*head, NULL);
}

### Q3. 針對 singly-linked list 中的節點，實作 Fisher-Yates shuffle。
流程如下：
1. 以一 `prev_head` 暫時節點，後方街上整個 list。
2. 先尋找到需要往後移的節點( `target` ) ，將其前方及後方接上
3. 再將 `destination` 移到目標地
4. 將 `target` 移到該處
5. 最後將適當的 head 回傳

void shuffle(node_t **head){
    // Find length of LL
    size_t length = 0;
    for(node_t *temp = *head; temp; temp = temp->next){
        ++length;
    }

    printf("Length of LL is %u.\n", length);

    // Fisher-Yates shuffle
    node_t *target = NULL, *prev = NULL, *destination = NULL;
    node_t *prev_head = malloc(sizeof(struct __node));
    prev_head->next = *head;
    int target_pos;
    srand(time(NULL));
    for(int i = length; i; --i){
        target_pos = rand() % i;
        printf("Shuffler picked index %d.\n", target_pos);
        
        // Get moving target
        target = prev_head->next;
        prev = prev_head;
        // printf("p @ [%p], t @ [%p], d @ [%p]\n", prev, target, destination);
        for(int j = target_pos; j; --j){
            prev = target;
            target = target->next;
        }

        // No need to swap
        if(!(i - target_pos - 1)){
            continue;
        }

        // Connect gap after getting the target
        prev->next = target->next;

        // Move to slot at position i - rand_result
        destination = target;
        for(int j = i - target_pos - 1; j; --j){
            destination = destination->next;
        }

        // Put target into designed destination
        target->next = destination->next;
        destination->next = target;

        print_list(prev_head->next);
        printf("\n");
    }
    *head = prev_head->next;
}

> TODO: 本實作需要在迴圈中判斷是否有移動必要；再嘗試將其解決