---
# System prepended metadata

title: 2020q3 Homework1 (quiz1)
tags: [sysprog2020]

---

# 2020q3 Homework1 (quiz1)
contribted by < `joe-U16` >
###### tags: `sysprog2020`

:::warning
由於對Git 的不熟悉，導致有兩個帳號commit 這個作業，但這兩個帳號都是我的。
Github 上commit 的有 \<papd32> \<joe-U16>
:::

Directory:
[toc]

## Node示意圖

* 單個節點
```graphviz

digraph foo {
        rankdir=LR;
        node [shape=record];
        a [label="{ node name | value | <ref> }"]
        a:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        
}    
```
* linked list，各節點名稱分別為a b c d，value 為 1 2 3 4

```graphviz
    digraph indirect{
        rankdir=LR;
        node [shape=record];
        a [label="{ <data> a | <value> 1 | <ref> }"];
        b [label="{ <data> b | <value> 2 | <ref> }"];
        c [label="{ <data> c | <value> 3 | <ref> }"];
        d [label="{ <data> d | <value> 4 | <ref> }"];
        
        
       
        a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c -> d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        
        d:ref:c -> NULL[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        }
```





## Q1

考慮一個單向 linked list，其結構定義為:
```cpp=
typedef struct __node {                   
    int value;
    struct __node *next;
} node_t;
```

已知不存在 circular (環狀結構)，接下來將對該單向 linked list 進行下列操作:

* ```add_entry```: 新增節點，當 linked list 沒有內容時，必須由開發者更新指向開頭的指標。因此實際得到 reference，而非 copy
* ```remove_entry```: 移除指定節點，指向開頭的指標可能因此變更，所以需要用到 a pointer to a pointer (指標的指標)
* ```swap_pair```: 交換一對相鄰的節點，取自 LeetCode: Swap Nodes in Pairs，給定 ```1->2->3->4```，則該回傳 ```2->1->4->3```
* ```reverse```: 將給定的 linked list 其內節點予以反向，即 ```1->2->3->4```，則該回傳 ```4->3->2->1```

### <font color=#4588C1>add_entry</font>

```cpp=
#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;

    assert(new_node); \\AA1
    while (*indirect)
        indirect = &(*indirect)->next;
    *indirect = new_node; \\AA2
}
```

* ==#13==幫new_node配置大小為```node_t```的記憶體
* ==#14==把new_value assign 給 new_node->value
* ==#15==new_node->next 指向 NULL
* ==#17==用[assert](https://pubs.opengroup.org/onlinepubs/9699919799/)判斷new_node 這個pointer variable的記憶體有沒有配置成功
```graphviz
    digraph foo {
        rankdir=LR;
        node [shape=record];
        a [label="{ new_node | new_value | <ref> }"]
        a:ref:c -> NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        
}
```
* ==#18==因為前面有```node_t **indirect = head;```，所以會從```head```開始，當```*indrect```還有東西，就持續前進


    1. 最初狀態
```graphviz
    digraph indirect{
        rankdir=LR;
        node [shape=record];
        
        a [label="{ <data> a | <value> 1 | <ref> }"];
        b [label="{ <data> b | <value> 2 | <ref> }"];
        c [label="{ <data> c | <value> 3 | <ref> }"];
        d [label="{ <data> d | <value> 4 | <ref> }"];
        
        indirect [label="{ indirect | <value> | <ref> }"];
        new_node [label="{ <data> new_node | <value> new_value| <ref>}"]
        valindirect [label="{ <data>*indirect | <value> | <ref> }"];
        head [label="{ <data> *head | <value> | <ref> }"];
        valhead [label="{ *head | <value> | <ref> }"];
        
        
        
        head -> valhead:value [arrowhead=ornomal]
        new_node:ref:c -> NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        valindirect -> a:value [arrowhead=onormal]
        indirect -> valindirect:value [arrowhead=onormal]
        valhead->a:value [arrowhead=onormal]
        
        
        
        
        
        
        a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c -> d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        d:ref:c -> NULL[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        }
```
2. 經過一次while迴圈，執行```indirect = new_node;```後
```graphviz
    digraph indirect{
        rankdir=LR;
        node [shape=record];
        a [label="{ <data> a | <value> 1 | <ref> }"];
        b [label="{ <data> b | <value> 2 | <ref> }"];
        c [label="{ <data> c | <value> 3 | <ref> }"];
        d [label="{ <data> d | <value> 4 | <ref> }"];
        
        indirect [label="{ indirect | <value> | <ref> }"];
        new_node [label="{ <data> new_node | <value> new_value| <ref>}"]
        valindirect [label="{ <data>*indirect | <value> | <ref> }"];
        head [label="{ <data> *head | <value> | <ref> }"];
        valhead [label="{ *head | <value> | <ref> }"];
        head -> valhead:value [arrowhead=ornomal]
        new_node:ref:c -> NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        
        valindirect -> b:value [arrowhead=onormal]
        indirect -> valindirect:value [arrowhead=onormal]
        valhead->a:value [arrowhead=onormal]
        a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c -> d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        
        d:ref:c -> NULL[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        }
```
3. 重複直到 *indirect is null

---

* ==#20==```*indirect = new_node; \\AA2```

```graphviz
    digraph indirect{
        rankdir=LR;
        node [shape=record];
        a [label="{ <data> a | <value> 1 | <ref> }"];
        b [label="{ <data> b | <value> 2 | <ref> }"];
        c [label="{ <data> c | <value> 3 | <ref> }"];
        d [label="{ <data> d | <value> 4 | <ref> }"];
        sizeof [label="{ <data>   | <value>   | <ref> }"];
        indirect [label="{ indirect | <value> | <ref> }"];
        new_node [label="{ <data> new_node | <value> new_value| <ref>}"]
        valindirect [label="{ <data>*indirect | <value> | <ref> }"];
        head [label="{ <data> *head | <value> | <ref> }"];
        valhead [label="{ *head | <value> | <ref> }"];
        head -> valhead:value [arrowhead=ornomal]
        new_node:ref:c -> NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        new_node -> sizeof [arrowhead=onormal]
        
        valindirect -> sizeof:value [arrowhead=onormal]
        indirect -> valindirect:value [arrowhead=onormal]
        valhead->a:value [arrowhead=onormal]
        a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c -> d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        
        d:ref:c -> NULL[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        }
```
---

### <font color="#4588C1">find_entry</font>

```cpp=
node_t *find_entry(node_t *head, int value)
{
    node_t *current = head;
    for (; current && current->value != value; current = current->next)
        /* interate */;
    return current;
}
```
* ==#3==current 這個pointer variable跟head存相同位址。
* ==#4==current有東西且current->value不等於value時，current移動到下一個位址
1. 初始狀態，current和head相同位址
```graphviz
    digraph indirect{
        rankdir=LR
        node [shape=record];
        {rank=same}
        a [label="{<data>  | <value>  | <ref>}"];
        b [label="{<data>  | <value>  | <ref>}"];
        head [label="{<data> head | <value> | <ref>}"];
        head -> a:value [arrowhead=ornomal]
        current [label="{<data> current | <value> | <ref>}"];
        current -> a:value [arrowhead=onormal]
        a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
2. current前進一格，判斷這個位子的value有沒有一樣，沒有的話繼續前進。  ==這邊假設在這裡找到value。==
```graphviz
    digraph indirect{
        rankdir=LR
        node [shape=record];
        nodea [label="{<A>  | <value>  | <ref>}"];
        nodeb [label="{<C>  | <value> value | <ref>}"];
        head [label="{<data> head | <value> | <ref>}"];
        head -> nodea:value [arrowhead=onormal]
        current [label="{<data> current | <value> | <ref>}"];
        current -> nodeb:value [arrowhead=onormal]
        nodea:ref:c -> nodeb:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```




3. 跳脫迴圈，回傳current 這個pointer variable

### <font color="#4588C1">remove_entry</font>
```cpp=
void remove_entry(node_t **head, node_t *entry)
{
    node_t **indirect = head;

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

    *indirect = entry->next;
    free(entry);
}
```
1. 初始狀態
* 假設entry在C節點
```graphviz
digraph graphname{
        node[shape=box]
        rankdir=LR
        head[shape=plaintext]
        indirect[shape=plaintext];
        NULL[shape=plaintext];
        n[shape=plaintext,label="entry"]
        {
        rank=same
        indirect->head->A
        }
        {
        rank=same
        n->C
        }
        
        A->B->C->D->NULL
    }
```
2. ==#5==一直前進下一個位址，直到找到entry;
```graphviz
digraph graphname{
        node[shape=box]
        rankdir=LR
        head[shape=plaintext]
        indirect[shape=plaintext];
        NULL[shape=plaintext];
        n[shape=plaintext,label="entry(*indirect)"]
        {
        rank=same
        head->A
        }
        {
        rank=same
        indirect->n->C
        }
        
        A->B->C->D->NULL
    }
```
3. ==#8==跳脫迴圈，```*indirect = entry->next``` *indirect會存entry的下一個位址，而entry最後釋放
```graphviz
digraph graphname{
        node[shape=box]
        rankdir=LR
        head[shape=plaintext]
        indirect[shape=plaintext];
        NULL[shape=plaintext];
        m[shape=plaintext,label="*indirect"]
        {
        rank=same
        head->A
        }
        {
        rank=same
        indirect->m->D
        }
        
        A->B->C->D->NULL
    }
```

<!--
```graphviz
    digraph indirect{
        rankdir=LR;
        node [shape=record];
        a [label="{ <data> a | <value>  | <ref> }"];
        b [label="{ <data> b | <value>  | <ref> }"];
        c [label="{ <data> c | <value>  | <ref> }"];
        
        entry [label="{ <data> entry | <value>  | <ref> }"];
        entry->b:value [arrowhead=onormal]
        
        headptr [label="{<headptr> headptr||}"]
        currentptr [label="{<currentptr> currentptr||}"]
        
        current [label="{ <data> current | <value> | <ref> }"];
        current -> a:value [arrowhead=onormal]
        head [label="{ <data> head | <value> | <ref> }"];
        head -> a:value [arrowhead=onormal]
        
        currentptr ->current:value [arrowhead=onormal]
        headptr ->head:value:n [arrowhead=onormal]
        
        a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c->NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```

```graphviz
    digraph indirect{
        rankdir=LR;
        node [shape=record];
        a [label="{ <data> a | <value>  | <ref> }"];
        b [label="{ <data> b | <value>  | <ref> }"];
        c [label="{ <data> c | <value>  | <ref> }"];
        
        entry [label="{ <data> entry | <value>  | <ref> }"];
        entry->b:value [arrowhead=onormal]
        
        headptr [label="{<headptr> headptr||}"]
        currentptr [label="{<currentptr> currentptr||}"]
        head [label="{ <data> head | <value> | <ref> }"];
        head -> a:value [arrowhead=onormal]
        current [label="{ <data> current | <value> | <ref> }"];
        current -> b:value [arrowhead=onormal]
        
        currentptr ->current:value [arrowhead=onormal]
        headptr ->head:value:n [arrowhead=onormal]
        
        a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c ->NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
3. 跳脫迴圈，*current存 entry下一個位址。
```graphviz
    digraph indirect{
        rankdir=LR;
        node [shape=record];
        a [label="{ <data> a | <value>  | <ref> }"];
        b [label="{ <data> b | <value>  | <ref> }"];
        c [label="{ <data> c | <value>  | <ref> }"];
        
        entry [label="{ <data> entry | <value>  | <ref> }"];
        entry->b:value [arrowhead=onormal]
        
        headptr [label="{<headptr> headptr||}"]
        currentptr [label="{<currentptr> currentptr||}"]
        head [label="{ <data> head | <value> | <ref> }"];
        head -> a:value [arrowhead=onormal]
        current [label="{ <data> current | <value> | <ref> }"];
        current -> c:value [arrowhead=onormal]
        
        currentptr ->current:value [arrowhead=onormal]
        headptr ->head:value:n [arrowhead=onormal]
        
        a:ref:c -> b:data; b:ref:c ->c:data  [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        //b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c ->NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
-->
4. 釋放entry;











### <font color="#4588C1">swap_pair</font>

```cpp=
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存head的address，只要目前這個位址和下個位址有值就持續執行
    1. ```node_t *tmp = *node;```
    ```graphviz
    digraph indirect{
        node [shape=record];
        rankdir=LR
        a [label="{<data> a | <value>  | <ref>}"];
        b [label="{<data> b | <value>  | <ref>}"];
        c [label="{<data> c | <value>  | <ref>}"];
        d [label="{<data> d | <value>  | <ref>}"];
        
        a:ref:c->b:data:c  [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        b:ref:c->c:data:c  [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c->d:data  [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        d->NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        
        head [label="{<data> *node | <value>  | <ref>}"];
        node1 [label="{<data> node | <value>  | <ref>}"];
        tmp [label="{<data> tmp | <value>  | <ref>}"];
        
        
        head->a:value [arrowhead=onormal]
        node1->head:value [arrowhead=onormal]
        tmp->a:value [arrowhead=onormal]
        
    }
    ```
    2. ```*node = (*node)->next;```
    ```graphviz
    digraph indirect{
        node [shape=record];
        rankdir=LR
        a [label="{<data> a | <value>  | <ref>}"];
        b [label="{<data> b | <value>  | <ref>}"];
        c [label="{<data> c | <value>  | <ref>}"];
        d [label="{<data> d | <value>  | <ref>}"];
        
        a:ref:c->b:data:c  [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        b:ref:c->c:data:c  [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c->d:data  [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        d->NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        
        
        
        head [label="{<data> *node | <value>  | <ref>}"];
        node1 [label="{<data> node | <value>  | <ref>}"];
        tmp [label="{<data> tmp | <value>  | <ref>}"];

        
        head->b:value [arrowhead=onormal]
        node1->head:value [arrowhead=onormal]
        tmp->a:value [arrowhead=onormal]   
    }
    ```
    3. ```tmp->next = (*node)->next```
     ```graphviz
    digraph indirect{
        node [shape=record];
        rankdir=LR
        a [label="{<data> a | <value>  | <ref>}"];
        b [label="{<data> b | <value>  | <ref>}"];
        c [label="{<data> c | <value>  | <ref>}"];
        d [label="{<data> d | <value>  | <ref>}"];
        
        a:ref:c->c:data:c  [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        b:ref:c->c:data:c  [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c->d:data  [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        d->NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        
        

        head [label="{<data> *node | <value>  | <ref>}"];
        node1 [label="{<data> node | <value>  | <ref>}"];
        tmp [label="{<data> tmp | <value>  | <ref>}"];

        
        head->b:value [arrowhead=onormal]
        node1->head:value [arrowhead=onormal]
        tmp:n->a:value [arrowhead=onormal]
    }
    ```
    4. ```(*node)->next = tmp;```
    ```graphviz
    digraph indirect{
        node [shape=record];
        rankdir=LR
        a [label="{<data> a | <value>  | <ref>}"];
        b [label="{<data> b | <value>  | <ref>}"];
        c [label="{<data> c | <value>  | <ref>}"];
        d [label="{<data> d | <value>  | <ref>}"];
        
        a:ref:c->c:data:c  [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        b:ref:c->a:data:c  [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c->d:data  [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        d->NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        
        
        head [label="{<data> *node | <value>  | <ref>}"];
        node1 [label="{<data> node | <value>  | <ref>}"];
        tmp [label="{<data> tmp | <value>  | <ref>}"];

        
        head->b:value [arrowhead=onormal]
        node1->head:value [arrowhead=onormal]
        tmp:n->a:value [arrowhead=onormal]
    }
    ```
* node 前進兩格
```graphviz
    digraph indirect{
        node [shape=record];
        rankdir=LR
        a [label="{<data> a | <value>  | <ref>}"];
        b [label="{<data> b | <value>  | <ref>}"];
        c [label="{<data> c | <value>  | <ref>}"];
        d [label="{<data> d | <value>  | <ref>}"];
        
        a:ref:c->c:data:c  [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        b:ref:c->a:data:c  [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c->d:data  [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        d->NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        
        
        head [label="{<data> *node | <value>  | <ref>}"];
        node1 [label="{<data> node | <value>  | <ref>}"];
        tmp [label="{<data> tmp | <value>  | <ref>}"];

        
        head->c:value [arrowhead=onormal]
        node1->head:value [arrowhead=onormal]
        tmp:n->a:value [arrowhead=onormal]
    }
```


### <font color="#4588C1">*reverse(node_t *head)</font>
```cpp=
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;
}
```

* ==#3==當head不為NULL時，重複1 2 3 4
```graphviz
    digraph indirect{
        node [shape=record];
        rankdir=LR
        a [label="{<data> a | <value>  | <ref>}"];
        b [label="{<data> b | <value>  | <ref>}"];
        c [label="{<data> c | <value>  | <ref>}"];
        d [label="{<data> d | <value>  | <ref>}"];
        
        a:ref:c->b:data:c  [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        b:ref:c->c:data:c  [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c->d:data  [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        d->NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        
        n [label="{NULL}"]
        head [label="{<data> head | <value>  | <ref>}"];
        head->a:value [arrowhead=onormal]
        cursor [label="{<data> cursor | <value>  | <ref>}"];
        cursor->n
        }
``` 
1. ```node_t *next = head->next;```
```graphviz
    digraph indirect{
        node [shape=record];
        rankdir=LR
        a [label="{<data> a | <value>  | <ref>}"];
        b [label="{<data> b | <value>  | <ref>}"];
        c [label="{<data> c | <value>  | <ref>}"];
        d [label="{<data> d | <value>  | <ref>}"];
        
        a:ref:c->b:data:c  [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        b:ref:c->c:data:c  [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c->d:data  [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        d->NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        
        n [label="{NULL}"]
        
        cursor [label="{<data> cursor | <value>  | <ref>}"];
        cursor->n [arrowhead=normal]
        head [label="{<data> head | <value>  | <ref>}"];
        head->a:value [arrowhead=onormal]
        next [label="{<data> next | <value>  | <ref>}"];
        next->b:value [arrowhead=onormal]    
        }
``` 
2. ```head->next = cursor;```
```graphviz
    digraph indirect{
        node [shape=record];
        rankdir=LR
        a [label="{<data> a | <value>  | <ref>}"];
        b [label="{<data> b | <value>  | <ref>}"];
        c [label="{<data> c | <value>  | <ref>}"];
        d [label="{<data> d | <value>  | <ref>}"];
        
        a:ref:c->n:data:c  [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        b:ref:c->c:data:c  [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c->d:data  [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        d->NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        
        n [label="{NULL}"]
        
        cursor [label="{<data> cursor | <value>  | <ref>}"];
        cursor->n [arrowhead=onormal]
        head [label="{<data> head | <value>  | <ref>}"];
        head->a:value [arrowhead=onormal]
        next [label="{<data> next | <value>  | <ref>}"];
        next->b:value [arrowhead=onormal]    
        }
``` 
3. ```cursor=head;```
```graphviz
    digraph indirect{
        node [shape=record];
        rankdir=LR
        a [label="{<data> a | <value>  | <ref>}"];
        b [label="{<data> b | <value>  | <ref>}"];
        c [label="{<data> c | <value>  | <ref>}"];
        d [label="{<data> d | <value>  | <ref>}"];
        
        a:ref:c->n:data:c  [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        b:ref:c->c:data:c  [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c->d:data  [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        d->NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        
        n [label="{NULL}"]
        
        cursor [label="{<data> cursor | <value>  | <ref>}"];
        cursor->a [arrowhead=onormal]
        head [label="{<data> head | <value>  | <ref>}"];
        head->a:value [arrowhead=onormal]
        next [label="{<data> next | <value>  | <ref>}"];
        next->b:value [arrowhead=onormal]    
        }
``` 
4. ```head = next```
```graphviz
    digraph indirect{
        node [shape=record];
        rankdir=LR
        a [label="{<data> a | <value>  | <ref>}"];
        b [label="{<data> b | <value>  | <ref>}"];
        c [label="{<data> c | <value>  | <ref>}"];
        d [label="{<data> d | <value>  | <ref>}"];
        
        a:ref:c->n:data:c  [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        b:ref:c->c:data:c  [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c->d:data  [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        d->NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        
        n [label="{NULL}"]
        
        cursor [label="{<data> cursor | <value>  | <ref>}"];
        cursor->a [arrowhead=onormal]
        head [label="{<data> head | <value>  | <ref>}"];
        head->b:value [arrowhead=onormal]
        next [label="{<data> next | <value>  | <ref>}"];
        next->b:value [arrowhead=onormal]    
        }
``` 
* 利用三個指標重複動作，最後將linked list 反轉。


## Q2 利用指標的指標改寫swap_pair、reverse避免回傳指標

* swap_pair
```cpp=
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;
    }
}
```
* reverse

```cpp=
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;
}
```

## Q3 以遞迴改寫上述的 reverse，注意，你可能因此需要建立新的函式，如 rev_recursive，隨後在 reverse 函式中呼叫 rev_recursive
* 初始狀態為
```graphviz
digraph name{
	node [shape=box]
	null [shape=plaintext]
	{
	rank=same
	a->b->c->d->null
	}
}
```
* 使用遞迴:step1
```graphviz
digraph name{
	node [shape=box]
	null [shape=plaintext]
	{
	rank=same
	cur [width=4]
	cur->a
	a->null
	
	}
}
```
* step2
```graphviz
digraph name{
	node [shape=box]
	null [shape=plaintext]
	{
	rank=same
	cur [width=3.5]
	cur->b->a
	a->null
	}
}
```
* 持續直到結束就完成啦

```cpp=
node_t *rev_reverse(node_t *head, node_t **pos)
{
    if(head->next) {
        node_t *tmp = rev_reverse(head->next, pos);
        tmp->next = head;
        head->next = NULL;
        return head;
        
    }
    *pos = head;
    return head;
}

void reverse(node_t **head)
{   
    if (!*head || !(*head)->next)
        return;
    node_t **pos;
    pos = head;
    
    rev_reverse(*head, pos);
    head = pos;
}
```

## Q4 針對 singly-linked list 的節點，實作 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher–Yates_shuffle)，你應該儘量降低記憶體的使用量;
```cpp=
void find_pos(node_t **tmp, uint16_t pos)
{   
    for (pos--;pos;pos--) {
        *tmp = (*tmp)->next;
    }
}

void shuffle(node_t **head)
{   
    uint16_t count = 0;
    for (node_t *current = *head; current; current = current->next) {
        count += 1;
    }
    if (count == 1)
        return;


    node_t *tail = NULL;
    node_t *cursor = *head;
    node_t *tmp = *head;
    uint16_t pos = rand() % count;
    if (pos == 0) {
        tail = cursor;
        cursor = cursor->next;
        count -= 1;
    } else {
        find_pos(&tmp, pos);
        node_t *target = tmp->next;
        tmp->next = target->next;
        target->next = cursor;
        tail = target;
        count -= 1;
    }
    *head = tail;

    for (count--; count; count--) {
        tmp = cursor;
        uint16_t pos = rand() % count;

        if (pos == 0) {
            tail = cursor;
            cursor = cursor->next;
            continue;
        }
        find_pos(&tmp, pos);
        node_t *target = tmp->next;
        tmp->next = target->next;
        target->next = cursor;
        tail->next = target;
        tail = tail->next;
    }
}
```



<!--
```graphviz
    digraph circle{
            a -> b;
            b -> c;
            c -> a;
            a -> b
    }
```
```graphviz
    digraph foo {
        rankdir=LR;
        node [shape=record];
        a [label="{ <data> 12 | <ref> }", width=1.2]
        b [label="{ <data> 99 | <ref> }"]
        c [label="{ <data> 37 | <ref> }"]
        d [shape=box];
        a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        a:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c -> d    [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        b:ref:c -> e    [arrowhead=vee]
}
```




```graphviz
    digraph indirect{
        node [shape=record];
        {rank=same; structa, structb}
        structa [label="<A> | |<ref>"]
        structb [label="<B> | |<ref>"]
        head [label="<head> head||"]
        current [label="<current> current ||"]
        
        //structa:ref -> :B:nw
        head -> structa [arrowhead=onormal]
        current -> structb [arrowhead=onormal]

    }
```

```graphviz
    digraph indirect{
            node [shape=record];
            {rank=same; structa, structc}
            structp [label="p|<p>&A"]
            structptr [label="<name_ptr> prtA | <ptr> &A"]
            structa [label="<A> A|1"];
            structc [label="<C> B|3"]; 
            structp:ptr->structptr:A:nw
            structptr:ptr -> structa:A:nw
            

            }
```

    
-->