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

## Outline
[TOC]

考慮一個單向 linked list，其結構定義為:

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

## 程式運作原理

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

    assert(new_node);
    while (*indirect)
        indirect = &(*indirect)->next;
    *indirect = new_node;
}

新增一個節點到 linked list 的尾端：

digraph G {
    graph[pencolor=transparent];
    rankdir=LR
    indirect[shape=none];
    head[shape=none];
    node_0[shape=box];
    node_1[shape=box];
    node_2[shape=box];
    NULL_1[shape=none,label="NULL"];
    NULL_2[shape=none,label="NULL"];
    new_node[shape=box];
    


    node_0->node_1->node_2->NULL_2;
    new_node->NULL_1;
    
    {rank=same;indirect->head->node_0;}
}

在這函式裡，首先建立了一個 `indirect` 指標指向 `head` 指標， `head` 則指向 linked list 的起點。

接著透過 malloc 新增一個節點的記憶體空間，這個節點會指向 NULL，經過 while 迴圈 ， `indirect` 會指向 linked list 最尾端NULL，此時將新節點指派給 `indirect` 完成新增節點。

digraph G {
    graph[pencolor=transparent];
    rankdir=LR
    indirect[shape=none];
    head[shape=none];
    node_0[shape=box];
    node_1[shape=box];
    node_2[shape=box];
    NULL_1[shape=none,label="NULL"];
    NULL_2[shape=none,label="NULL"];
    new_node[shape=box];
    


    node_0->node_1->node_2->NULL_2;
    new_node->NULL_1;
    
    {rank=same;head->node_0;}

    {rank=same;indirect->NULL_2;}
}

digraph G {
    graph[pencolor=transparent];

    indirect[shape=none];
    head[shape=none];
    node_0[shape=box];
    node_1[shape=box];
    node_2[shape=box];
    NULL_1[shape=none,label="NULL"];
    new_node[shape=box];
    

    {rank=same;
    node_0->node_1->node_2->new_node->NULL_1;}
    head->node_0;

    indirect->new_node;
}

* 此函式中的 `assert(new_node);` 目的是為了要確保新的節點有成功 malloc (NULL 失敗)，因此 `AA1` 為 `assert(new_node);`
* `AA2` 答案為 `*indirect = new_node` 是因為需要得知 linked list 最尾端的位置在何處。

### find_entry

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 的頭開始遍歷，直到找到符合的節點後回傳該節點。

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

移除某個節點（entry），類似 `add_entry` 的做法，詳細如下：

digraph G {
    graph[pencolor=transparent];
    rankdir=LR
    indirect[shape=none];
    head[shape=none];
    node_0[shape=box];
    node_1[shape=box];
    node_2[shape=box];
    node_3[shape=box];
    NULL_1[shape=none,label="NULL"];
    delete[shape=none,label="want_to_delete"];
    node_0->node_1->node_2->node_3->NULL_1; 
    {rank=same;indirect->head->node_0;}
    {rank=same; delete->node_2}
}

經由 while 迴圈找到該 entry

digraph G {
    graph[pencolor=transparent];
    rankdir=LR
    indirect[shape=none];
    head[shape=none];
    node_0[shape=box];
    node_1[shape=box];
    node_2[shape=box];
    node_3[shape=box];
    NULL_1[shape=none,label="NULL"];
    delete[shape=none,label="want_to_delete_entry"];
    node_0->node_1->node_2->node_3->NULL_1; 
    {rank=same;head->node_0;}
    {rank=same; indirect->delete->node_2}
}

更換 indirect 指向的記憶體空間，再 free entry。

digraph G {
    graph[pencolor=transparent];
    rankdir=LR
    indirect[shape=none];
    head[shape=none];
    node_0[shape=box];
    node_1[shape=box];
    node_2[shape=box];
    node_3[shape=box];
    NULL_1[shape=none,label="NULL"];
    delete[shape=none,label="want_to_delete_entry"];
    node_0->node_1->node_3->NULL_1; 
    {rank=same;head->node_0;}
    {rank=same; delete->node_2}
    {rank=same; indirect->node_3}
}

### swap_pair

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

`node_0` 和 `node_1` 交換， `node_2` 和 `node_3` 交換，以次類推。
這裡的做法也是使用指標的指標來做操作。

一開始進入迴圈時長這樣， node 指標指向 head 指標。

digraph G {
    graph[pencolor=transparent];
    rankdir=LR
    head[shape=none];
    n[shape=none,label="node"];
    node_0[shape=box];
    node_1[shape=box];
    node_2[shape=box];
    node_3[shape=box];
    NULL_1[shape=none,label="NULL"];

    node_0->node_1->node_2->node_3->NULL_1; 
    {rank=same;n->head->node_0;}
}

宣告 tmp 指向 *node（head 指標）。

digraph G {
    graph[pencolor=transparent];
    rankdir=LR
    head[shape=none];
    n[shape=none,label="node"];
    node_0[shape=box];
    tmp[shape=none]
    node_1[shape=box];
    node_2[shape=box];
    node_3[shape=box];
    NULL_1[shape=none,label="NULL"];

    node_0->node_1->node_2->node_3->NULL_1; 
    {rank=same;n->head->node_0;}
    tmp->node_0;
}

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

node 新位址指向 node 的下個節點的位址。因此 `BB2` 答案為 `*node = (*node)->next;`

digraph G {
    graph[pencolor=transparent];
    rankdir=LR
    head[shape=none];
    n[shape=none,label="node"];
    node_0[shape=box];
    tmp[shape=none]
    node_1[shape=box];
    node_2[shape=box];
    node_3[shape=box];
    NULL_1[shape=none,label="NULL"];

    node_0->node_1->node_2->node_3->NULL_1; 
    {rank=same;n->head->node_1}
    {rank=same;tmp->node_0;}
}

`tmp->next = (*node)->next;`
tmp 新位址指向 node 下一個的位址。

digraph G {
    graph[pencolor=transparent];
    rankdir=LR
    head[shape=none];
    n[shape=none,label="node"];
    node_0[shape=box];
    tmp[shape=none]
    node_1[shape=box];
    node_2[shape=box];
    node_3[shape=box];
    NULL_1[shape=none,label="NULL"];

    node_1->node_2->node_3->NULL_1; 
    {rank=same;n->head->node_1}
    {rank=same;tmp->node_0->node_2;}
}

node 指向 tmp 完成交換。

digraph G {
    graph[pencolor=transparent];
    rankdir=LR
    head[shape=none];
    n[shape=none,label="node"];
    node_0[shape=box];
    tmp[shape=none]
    node_1[shape=box];
    node_2[shape=box];
    node_3[shape=box];
    NULL_1[shape=none,label="NULL"];

    node_1->node_0->node_2->node_3->NULL_1; 
    {rank=same;n->head->node_1}
    {rank=same;tmp->node_0}
}

因為是兩倆交換，因此 node 在每次 iteration 完都要 往前兩格，所以 `BB1` 為 `node = &(*node)->next->next`

digraph G {
    graph[pencolor=transparent];
    rankdir=LR
    head[shape=none];
    n[shape=none,label="node"];
    node_0[shape=box];
    tmp[shape=none]
    node_1[shape=box];
    node_2[shape=box];
    node_3[shape=box];
    NULL_1[shape=none,label="NULL"];

    node_1->node_0->node_2->node_3->NULL_1; 
    {rank=same;head->node_1}
    {rank=same;tmp->node_0}
    {rank=same;n->node_2}
}

### reverse

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

做 linked list 反轉，一開始大概是長這樣。

digraph G {
    graph[pencolor=transparent];
    rankdir=LR
    head[shape=none];
    node_0[shape=box];
    cursor[shape=none];
    node_1[shape=box];
    node_2[shape=box];
    node_3[shape=box];
    NULL_1[shape=none,label="NULL"];
    NULL_2[shape=none,label="NULL"];
    node_0->node_1->node_2->node_3->NULL_1; 
    {rank=same;head->node_0}
    rank=same;cursor->NULL_2
}

`node_t *next = head->next;` ， next 指標指向 head 的 next。

digraph G {
    graph[pencolor=transparent];
    rankdir=LR
    head[shape=none];
    next[shape=none];
    node_0[shape=box];
    cursor[shape=none];
    node_1[shape=box];
    node_2[shape=box];
    node_3[shape=box];
    NULL_1[shape=none,label="NULL"];
    NULL_2[shape=none,label="NULL"];
    node_0->node_1->node_2->node_3->NULL_1; 
    {rank=same;head->node_0}
    {rank=same;next->node_1}
    cursor->NULL_2
}

`CCC` 是 `head->next = cursor; cursor = head;` ，其中 cursor 是用來記住 head 前一個節點使得之後可以被指向，達成反轉的效果。

digraph G {
    graph[pencolor=transparent];
    rankdir=LR
    head[shape=none];
    next[shape=none];
    node_0[shape=box];
    cursor[shape=none];
    node_1[shape=box];
    node_2[shape=box];
    node_3[shape=box];
    NULL_1[shape=none,label="NULL"];
    NULL_2[shape=none,label="NULL"];
    node_0->node_1->node_2->node_3->NULL_1; 
    {rank=same;head->node_0}
    {rank=same;next->node_1}
    {rank=same;cursor->node_0;}
    rank=same;node_0->NULL_2;
}

`head = next;` ，遍歷下去後直到 head = NULL，回傳 cursor 做為新的 head。

digraph G {
    graph[pencolor=transparent];
    rankdir=LR

    next[shape=none,label="next(head)"];
    node_0[shape=box];
    cursor[shape=none];
    node_1[shape=box];
    node_2[shape=box];
    node_3[shape=box];
    NULL_1[shape=none,label="NULL"];
    NULL_2[shape=none,label="NULL"];
    node_0->node_1->node_2->node_3->NULL_1; 
    {rank=same;next->node_1}
    {rank=same;cursor->node_0;}
    rank=same;node_0->NULL_2;
}

## 延伸問題

避免函式回傳指標。

### swap_pair

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

其實原本的寫法就可以說是指標的指標的操作，只是還需要回傳 head ，因此稍微改一下，將傳入的參數改成是傳位址，用 node 去接這個傳入的參數，變相利用 node 當作 head 進行操作。

### reverse

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

一樣也是傳 head 的位址參數到函式中，概念就和原先的方式一樣，比較要注意的地方是在最後要把 cursor 指標 指派給 *head 。

### 遞迴版 reverse

void reverse(node_t **head)
{
    rev_recurive(*head,  head);
}

void rev_recurive(node_t *head, node_t **headRef)
{
    if (head == NULL) {
        return;
    } 
    node_t *first = head;
    node_t *rest = head->next;
    if (rest == NULL) {
        *headRef = first;
        return;
    }
    rev_recurive(rest, headRef);
    rest->next = first;
    first->next = NULL;
}

遞迴的概念是將 linked list 分成 第一個節點 ( `first` ) 和剩下其他的節點們 ( `rest` ) 遞迴拆解下去。遞迴函式傳入的會是 `head` 指標和 `head` 指標的位址，此方式是為了避免回傳指標。
從 `reverse` call `rev_recurive` 函式後，在進入 `rev_recurive` 函式之前的狀態會長這樣。

digraph G {
    graph[pencolor=transparent];
    rankdir=LR
    rest[shape=none];
    node_0[shape=box];
    head[shape=none,label="first"];
    node_1[shape=box];
    node_2[shape=box];
    NULL_1[shape=none, label="NULL"];
    node_0->node_1->node_2->NULL_1; 
    {rank=same;head->node_0}
    {rank=same;rest->node_1}
}

進入 `rev_recurive` 後， `first` 和 `rest` 會更新成下面這樣。

digraph G {
    graph[pencolor=transparent];
    rankdir=LR
    rest[shape=none];
    node_0[shape=box];
    head[shape=none,label="first"];
    node_1[shape=box];
    node_2[shape=box];
    NULL_1[shape=none, label="NULL"];
    node_0->node_1->node_2->NULL_1; 
    {rank=same;head->node_1}
    {rank=same;rest->node_2}
}

一直遞迴下去，直到 `rest` 碰到 `NULL` 進入 if 判斷式。

digraph G {
    graph[pencolor=transparent];
    rankdir=LR
    rest[shape=none];
    node_0[shape=box];
    head[shape=none,label="first"];
    node_1[shape=box];
    node_2[shape=box];
    NULL_1[shape=none, label="NULL"];
    node_0->node_1->node_2->NULL_1; 
    {rank=same;head->node_2}
    {rank=same;rest->NULL_1}
}

在 if 在判斷式中將目前 `first` 節點的位址指派給 `headRef` 目的是為了將 linked list 最後面節點的位址指派給原先傳進來的 head 位址。之後return 。

digraph G {
    graph[pencolor=transparent];
    rankdir=LR
    rest[shape=none];
    node_0[shape=box];
    head[shape=none,label="first"];
    headRef[shape=none];
    node_1[shape=box];
    node_2[shape=box];
    NULL_1[shape=none, label="NULL"];
    node_0->node_1->node_2->NULL_1; 
    {rank=same;headRef->head->node_2}
    {rank=same;rest->NULL_1}
}

return 之後，繼續往下做還沒做完的事情，因為 return 回到遞迴的前一層，所以 `rest` 跑回 `first` 的位置， `first` 跑回指向前一個 node（回到進到函式前的狀態）。

digraph G {
    graph[pencolor=transparent];
    rankdir=LR
    rest[shape=none];
    node_0[shape=box];
    head[shape=none,label="first"];
    headRef[shape=none];
    node_1[shape=box];
    node_2[shape=box];
    NULL_1[shape=none, label="NULL"];
    node_0->node_1->node_2->NULL_1;
    {rank=same;headRef->rest->node_2}
    {rank=same;head->node_1}
}

繼續完成沒做完的事， `rest` 指向 `first` 指向的節點， `first` 指向的節點指向 `NULL`。此次的函式執行完畢，返回上一層遞迴。

digraph G {
    graph[pencolor=transparent];
    rankdir=LR;
    rest[shape=none];
    node_0[shape=box];
    NULL_1[shape=none, label="NULL"];
    head[shape=none,label="first"];
    headRef[shape=none];
    node_1[shape=box];
    node_2[shape=box];
    node_0->node_1;
    
    {rank=same;headRef->rest->node_2}
    {rank=same;head->node_1}
    node_2->node_1->NULL_1
}

一樣 `rest` 跑回 `first` 的位置， `first` 跑回指向前一個 node。

digraph G {
    graph[pencolor=transparent];
    rankdir=LR;
    rest[shape=none];
    node_0[shape=box];
    NULL_1[shape=none, label="NULL"];
    head[shape=none,label="first"];
    headRef[shape=none];
    node_1[shape=box];
    node_2[shape=box];
    node_0->node_1;
    {rank=same;headRef->node_2};
    {rank=same;rest->node_1}
    {rank=same;head->node_0}
    node_2->node_1->NULL_1
}

和前一次的遞迴一樣做完剩下的工作。

digraph G {
    graph[pencolor=transparent];
    rankdir=LR;
    rest[shape=none];
    node_0[shape=box];
    NULL_1[shape=none, label="NULL"];
    head[shape=none,label="first"];
    headRef[shape=none];
    node_1[shape=box];
    node_2[shape=box];
    node_1->node_0->NULL_1;
    {rank=same;headRef->node_2};
    {rank=same;rest->node_1}
    {rank=same;head->node_0}
    node_2->node_1
}

### Fisher–Yates shuffle

參考 [wiki, Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle)進行實作。

void shuffle(node_t **head)
{
    int len = 0;
    srand(time(NULL));
    node_t **cursor = head;
    while(*cursor) {
        len++;
        cursor = &(*cursor)->next;
    }
    
    node_t *first = NULL;
    for (int i = len; i > 0; i--) {
        int random = rand() % i;
        cursor = head;
        while (random--) {
            cursor = &(*cursor)->next;
        }
        node_t *new_node = *cursor;
        *cursor = (*cursor)->next;
        new_node->next = NULL;
        if (first) {
            new_node->next = first;
            first = new_node;
        } else {
            first = new_node;
        }
    }
    *head = first;
}

* 一開始會去計算整個 linked list 的長度有多長。知道長度後就開始進入該演算法的實作。
* 一開始會宣告 `first` ，這是待會要指派給 head 的新的 linked list 的頭。
* 隨後 `cursor` 會去找被挑選中的 node 。
* 找到後會有一個 `new_node` 指標去指向這個被找到的 node 。而 `cursor` 則將此 node 的前一個和後一個的 node 連接。
* `new_node` append 到剛剛的 `first` 。直到迴圈結束。
* 迴圈結束後，將原先的 `head` 的更換為 `first` 。

:::warning
延伸問題 :fire: :fire: :fire:
* 思考可能的更好的寫法，能否降低時間複雜度。
* 或是其他更好的洗牌演算法。
:::