---
# System prepended metadata

title: 2020q3 Homework1 (quiz1)

---

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

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

## 1. 解釋上述程式運作原理，搭配 [Graphviz](https://graphviz.org/)，比照 [Linked List 練習題](https://hackmd.io/@sysprog/linked-list-quiz) 在 HackMD 筆記上視覺化展現
```cpp=
#include <assert.h>
#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));
    /* AA1: a */
    assert(new_node);
    new_node->value = new_value;
    new_node->next = NULL;

    while (*indirect)
        indirect = &(*indirect)->next;
    /* AA2: b */
    *indirect = new_node;
}

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: e */ node = &(*node)->next->next) {
        node_t *tmp = *node;
        /* BB2: c */
        *node = (*node)->next;
        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: b */
        head->next = cursor;
        cursor = head;
        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;
}
```

### node_t 
```graphviz
digraph node_t {
    rankdir=LR;
    node [shape=Mrecord, color=black];
    node_t [label="{ <data> value | <ref> *next }"];
}
```
### add_entry
加入第二筆資料時追蹤 add_entry
```cpp
add_entry(&head, 72);
add_entry(&head, 101);
```
傳入 main function 的 head 位址 &(main.head)
```cpp
void add_entry(node_t **head, int new_value)
{
    node_t **indirect = head;

    node_t *new_node = malloc(sizeof(node_t));
    /* AA1: a */
    assert(new_node);
    new_node->value = new_value;
    new_node->next = NULL;
```
```graphviz
digraph linkedlist {
    rankdir=LR;
    node [shape=record, color=indigo]; head; indirect;
    node [shape=record, color=forestgreen]; address_of_head [label="main.head", fontcolor=blue]; new_node;
    node [shape=Mrecord, color=black]; first [label="{ <data> 72 | <ref> }"]; new [label="{ <data> 101 | <ref> }"];
    node [shape=none]; null [label="NULL"];

    address_of_head -> first [arrowhead=vee, arrowtail=dot, dir=both];
    head -> address_of_head [arrowhead=vee, arrowtail=crow, dir=both];
    indirect -> address_of_head [arrowhead=vee, arrowtail=crow, dir=both];
    first:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    new_node -> new [arrowhead=vee, arrowtail=dot, dir=both];
    new:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
```cpp
    while (*indirect)
        indirect = &(*indirect)->next;
```
```graphviz
digraph linkedlist {
    rankdir=LR;
    node [shape=record, color=indigo]; head; indirect;
    node [shape=record, color=forestgreen]; address_of_head [label="main.head", fontcolor=blue]; new_node;
    node [shape=Mrecord, color=black]; first [label="{ <data> 72 | <ref> }"]; new [label="{ <data> 101 | <ref> }"];
    node [shape=none]; null [label="NULL"];

    address_of_head -> first [arrowhead=vee, arrowtail=dot, dir=both];
    head -> address_of_head [arrowhead=vee, arrowtail=crow, dir=both];
    first:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    new_node -> new [arrowhead=vee, arrowtail=dot, dir=both];
    new:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    indirect -> first:ref [arrowhead=vee, arrowtail=crow, dir=both, color=red];
}
```
```cpp
    *indirect = new_node;
}
```
```graphviz
digraph linkedlist {
    rankdir=LR;
    node [shape=record, color=indigo]; head; indirect;
    node [shape=record, color=forestgreen]; address_of_head [label="main.head", fontcolor=blue]; new_node;
    node [shape=Mrecord, color=black]; first [label="{ <data> 72 | <ref> }"]; new [label="{ <data> 101 | <ref> }"];
    node [shape=none]; null [label="NULL"];

    address_of_head -> first [arrowhead=vee, arrowtail=dot, dir=both];
    head -> address_of_head [arrowhead=vee, arrowtail=crow, dir=both];
    indirect -> first:ref [arrowhead=vee, arrowtail=crow, dir=both];
    new_node -> new [arrowhead=vee, arrowtail=dot, dir=both];
    new:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    first:ref:c -> new [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, color=red];
}
```

### swap_pair
```cpp
node_t *swap_pair(node_t *head)
{
    for (node_t **node = &head; ...; ...) {
        node_t *tmp = *node;
```
```graphviz
digraph linkedlist {
    rankdir=LR;
    node [shape=record, color=indigo]; n [label="node"];
    node [shape=record, color=forestgreen]; head; tmp;
    node [shape=Mrecord, color=black];
    first [label="{ <data> 72 | <ref> }"];
    second [label="{ <data> 108 | <ref> }"];
    third [label="{ <data> 109 | <ref> }"];
    fourth [label="{ <data> 110 | <ref> }"];
    node [shape=none]; null [label="NULL"];

    head -> first [arrowhead=vee, arrowtail=dot, dir=both];
    n -> head [arrowhead=vee, arrowtail=crow, dir=both];
    first:ref:c -> second [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    second:ref:c -> third [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    third:ref:c -> fourth [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    fourth:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    tmp -> first [arrowhead=vee, arrowtail=dot, dir=both];
}
```
```cpp
        *node = (*node)->next;
```
```graphviz
digraph linkedlist {
    rankdir=LR;
    node [shape=record, color=indigo]; n [label="node"];
    node [shape=record, color=forestgreen]; head; tmp;
    node [shape=Mrecord, color=black];
    first [label="{ <data> 72 | <ref> }"];
    second [label="{ <data> 108 | <ref> }"];
    third [label="{ <data> 109 | <ref> }"];
    fourth [label="{ <data> 110 | <ref> }"];
    node [shape=none]; null [label="NULL"];

    n -> head [arrowhead=vee, arrowtail=crow, dir=both];
    first:ref:c -> second [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    second:ref:c -> third [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    third:ref:c -> fourth [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    fourth:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    tmp -> first [arrowhead=vee, arrowtail=dot, dir=both];
    head -> second [arrowhead=vee, arrowtail=dot, dir=both, color=red];
}
```
```cpp
        tmp->next = (*node)->next;
```
```graphviz
digraph linkedlist {
    rankdir=LR;
    node [shape=record, color=indigo]; n [label="node"];
    node [shape=record, color=forestgreen]; head; tmp;
    node [shape=Mrecord, color=black];
    first [label="{ <data> 72 | <ref> }"];
    second [label="{ <data> 108 | <ref> }"];
    third [label="{ <data> 109 | <ref> }"];
    fourth [label="{ <data> 110 | <ref> }"];
    node [shape=none]; null [label="NULL"];

    head -> second [arrowhead=vee, arrowtail=dot, dir=both];
    n -> head [arrowhead=vee, arrowtail=crow, dir=both];
    second:ref:c -> third [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    third:ref:c -> fourth [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    fourth:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    tmp -> first [arrowhead=vee, arrowtail=dot, dir=both];
    first:ref:c -> third [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, color=red];
}
```
```cpp
        (*node)->next = tmp;
    }
```
```graphviz
digraph linkedlist {
    rankdir=LR;
    node [shape=record, color=indigo]; n [label="node"];
    node [shape=record, color=forestgreen]; head; tmp;
    node [shape=Mrecord, color=black];
    first [label="{ <data> 72 | <ref> }"];
    second [label="{ <data> 108 | <ref> }"];
    third [label="{ <data> 109 | <ref> }"];
    fourth [label="{ <data> 110 | <ref> }"];
    node [shape=none]; null [label="NULL"];

    head -> second [arrowhead=vee, arrowtail=dot, dir=both];
    n -> head [arrowhead=vee, arrowtail=crow, dir=both];
    first:ref:c -> third [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    third:ref:c -> fourth [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    fourth:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    tmp -> first [arrowhead=vee, arrowtail=dot, dir=both];
    second:ref:c -> first [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, color=red];
}
```
```cpp
    for (...; *node && (*node)->next; node = &(*node)->next->next) {
        node_t *tmp = *node;
```
```graphviz
digraph linkedlist {
    rankdir=LR;
    node [shape=record, color=indigo]; n [label="node"];
    node [shape=record, color=forestgreen]; head; tmp;
    node [shape=Mrecord, color=black];
    first [label="{ <data> 72 | <ref> }"];
    second [label="{ <data> 108 | <ref> }"];
    third [label="{ <data> 109 | <ref> }"];
    fourth [label="{ <data> 110 | <ref> }"];
    node [shape=none]; null [label="NULL"];

    head -> second [arrowhead=vee, arrowtail=dot, dir=both];
    first:ref:c -> third [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    second:ref:c -> first [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    third:ref:c -> fourth [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    fourth:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    n -> first:ref [arrowhead=vee, arrowtail=crow, dir=both, color=red];
    tmp -> third [arrowhead=vee, arrowtail=dot, dir=both, color=red];
}
```
```cpp
        *node = (*node)->next;
```
```graphviz
digraph linkedlist {
    rankdir=LR;
    node [shape=record, color=indigo]; n [label="node"];
    node [shape=record, color=forestgreen]; head; tmp;
    node [shape=Mrecord, color=black];
    first [label="{ <data> 72 | <ref> }"];
    second [label="{ <data> 108 | <ref> }"];
    third [label="{ <data> 109 | <ref> }"];
    fourth [label="{ <data> 110 | <ref> }"];
    node [shape=none]; null [label="NULL"];

    head -> second [arrowhead=vee, arrowtail=dot, dir=both];
    second:ref:c -> first [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    third:ref:c -> fourth [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    fourth:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    n -> first:ref [arrowhead=vee, arrowtail=crow, dir=both];
    tmp -> third [arrowhead=vee, arrowtail=dot, dir=both];
    first:ref:c -> fourth [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, color=red];
}
```
```cpp
        tmp->next = (*node)->next;
```
```graphviz
digraph linkedlist {
    rankdir=LR;
    node [shape=record, color=indigo]; n [label="node"];
    node [shape=record, color=forestgreen]; head; tmp;
    node [shape=Mrecord, color=black];
    first [label="{ <data> 72 | <ref> }"];
    second [label="{ <data> 108 | <ref> }"];
    third [label="{ <data> 109 | <ref> }"];
    fourth [label="{ <data> 110 | <ref> }"];
    node [shape=none]; null [label="NULL"];

    head -> second [arrowhead=vee, arrowtail=dot, dir=both];
    second:ref:c -> first [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    fourth:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    n -> first:ref [arrowhead=vee, arrowtail=crow, dir=both];
    tmp -> third [arrowhead=vee, arrowtail=dot, dir=both];
    first:ref:c -> fourth [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    third:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, color=red];
}
```
```cpp
        (*node)->next = tmp;
    }
```
```graphviz
digraph linkedlist {
    rankdir=LR;
    node [shape=record, color=indigo]; n [label="node"];
    node [shape=record, color=forestgreen]; head; tmp;
    node [shape=Mrecord, color=black];
    first [label="{ <data> 72 | <ref> }"];
    second [label="{ <data> 108 | <ref> }"];
    third [label="{ <data> 109 | <ref> }"];
    fourth [label="{ <data> 110 | <ref> }"];
    node [shape=none]; null [label="NULL"];

    head -> second [arrowhead=vee, arrowtail=dot, dir=both];
    second:ref:c -> first [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    n -> first:ref [arrowhead=vee, arrowtail=crow, dir=both];
    tmp -> third [arrowhead=vee, arrowtail=dot, dir=both];
    first:ref:c -> fourth [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    third:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    fourth:ref:c -> third [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, color=red];
}
```
```cpp
    for (...; *node && (*node)->next; node = &(*node)->next->next) {
        ...
    }
    return head;
}
```
```graphviz
digraph linkedlist {
    rankdir=LR;
    node [shape=record, color=indigo]; n [label="node"];
    node [shape=record]; head;
    node [shape=Mrecord, color=black];
    first [label="{ <data> 72 | <ref> }"];
    second [label="{ <data> 108 | <ref> }"];
    third [label="{ <data> 109 | <ref> }"];
    fourth [label="{ <data> 110 | <ref> }"];
    node [shape=none]; null [label="NULL"];

    head -> second [arrowhead=vee, arrowtail=dot, dir=both];
    second:ref:c -> first [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    first:ref:c -> fourth [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    third:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    fourth:ref:c -> third [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    n -> third:ref [arrowhead=vee, arrowtail=crow, dir=both, color=red];
}
```

### reverse
```cpp
node_t *reverse(node_t *head)
{
    node_t *cursor = NULL;
```
```graphviz
digraph linkedlist {
    rankdir=LR;
    node [shape=record, color=forestgreen]; head; cursor;
    node [shape=Mrecord, color=black];
    first [label="{ <data> 108 | <ref> }"];
    second [label="{ <data> 72 | <ref> }"];
    third [label="{ <data> 110 | <ref> }"];
    fourth [label="{ <data> 109 | <ref> }"];
    node [shape=none]; null [label="NULL"];

    head -> first [arrowhead=vee, arrowtail=dot, dir=both];
    first:ref:c -> second [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    second:ref:c -> third [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    third:ref:c -> fourth [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    fourth:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    cursor -> null [arrowhead=vee, arrowtail=dot, dir=both];
}
```
Round 1
```cpp
    while (head) {
        node_t *next = head->next;
```
```graphviz
digraph linkedlist {
    rankdir=LR;
    node [shape=record, color=forestgreen]; head; cursor; next;
    node [shape=Mrecord, color=black];
    first [label="{ <data> 108 | <ref> }"];
    second [label="{ <data> 72 | <ref> }"];
    third [label="{ <data> 110 | <ref> }"];
    fourth [label="{ <data> 109 | <ref> }"];
    node [shape=none]; null [label="NULL"];

    head -> first [arrowhead=vee, arrowtail=dot, dir=both];
    first:ref:c -> second [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    second:ref:c -> third [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    third:ref:c -> fourth [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    fourth:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    cursor -> null [arrowhead=vee, arrowtail=dot, dir=both];
    next -> second [arrowhead=vee, arrowtail=dot, dir=both, color=red];
}
```
```cpp
        head->next = cursor;
```
```graphviz
digraph linkedlist {
    rankdir=LR;
    node [shape=record, color=forestgreen]; head; cursor; next;
    node [shape=Mrecord, color=black];
    first [label="{ <data> 108 | <ref> }"];
    second [label="{ <data> 72 | <ref> }"];
    third [label="{ <data> 110 | <ref> }"];
    fourth [label="{ <data> 109 | <ref> }"];
    node [shape=none]; null [label="NULL"];

    head -> first [arrowhead=vee, arrowtail=dot, dir=both];
    second:ref:c -> third [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    third:ref:c -> fourth [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    fourth:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    cursor -> null [arrowhead=vee, arrowtail=dot, dir=both];
    next -> second [arrowhead=vee, arrowtail=dot, dir=both];
    first:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, color=red];
}
```
```cpp
        cursor = head;
```
```graphviz
digraph linkedlist {
    rankdir=LR;
    node [shape=record, color=forestgreen]; head; cursor; next;
    node [shape=Mrecord, color=black];
    first [label="{ <data> 108 | <ref> }"];
    second [label="{ <data> 72 | <ref> }"];
    third [label="{ <data> 110 | <ref> }"];
    fourth [label="{ <data> 109 | <ref> }"];
    node [shape=none]; null [label="NULL"];

    head -> first [arrowhead=vee, arrowtail=dot, dir=both];
    second:ref:c -> third [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    third:ref:c -> fourth [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    fourth:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    next -> second [arrowhead=vee, arrowtail=dot, dir=both];
    first:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    cursor -> first [arrowhead=vee, arrowtail=dot, dir=both, color=red];
}
```
```cpp
        head = next;
    }
```
```graphviz
digraph linkedlist {
    rankdir=LR;
    node [shape=record, color=forestgreen]; head; cursor; next;
    node [shape=Mrecord, color=black];
    first [label="{ <data> 108 | <ref> }"];
    second [label="{ <data> 72 | <ref> }"];
    third [label="{ <data> 110 | <ref> }"];
    fourth [label="{ <data> 109 | <ref> }"];
    node [shape=none]; null [label="NULL"];

    second:ref:c -> third [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    third:ref:c -> fourth [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    fourth:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    next -> second [arrowhead=vee, arrowtail=dot, dir=both];
    first:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    cursor -> first [arrowhead=vee, arrowtail=dot, dir=both];
    head -> second [arrowhead=vee, arrowtail=dot, dir=both, color=red];
}
```
Round 2
```cpp
    while (head) {
        node_t *next = head->next;
```
```graphviz
digraph linkedlist {
    rankdir=LR;
    node [shape=record, color=forestgreen]; head; cursor; next;
    node [shape=Mrecord, color=black];
    first [label="{ <data> 108 | <ref> }"];
    second [label="{ <data> 72 | <ref> }"];
    third [label="{ <data> 110 | <ref> }"];
    fourth [label="{ <data> 109 | <ref> }"];
    node [shape=none]; null [label="NULL"];

    second:ref:c -> third [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    third:ref:c -> fourth [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    fourth:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    first:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    cursor -> first [arrowhead=vee, arrowtail=dot, dir=both];
    head -> second [arrowhead=vee, arrowtail=dot, dir=both];
    next -> third [arrowhead=vee, arrowtail=dot, dir=both, color=red];
}
```
```cpp
        head->next = cursor;
```
```graphviz
digraph linkedlist {
    rankdir=LR;
    node [shape=record, color=forestgreen]; head; cursor; next;
    node [shape=Mrecord, color=black];
    first [label="{ <data> 108 | <ref> }"];
    second [label="{ <data> 72 | <ref> }"];
    third [label="{ <data> 110 | <ref> }"];
    fourth [label="{ <data> 109 | <ref> }"];
    node [shape=none]; null [label="NULL"];

    third:ref:c -> fourth [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    fourth:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    first:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    cursor -> first [arrowhead=vee, arrowtail=dot, dir=both];
    head -> second [arrowhead=vee, arrowtail=dot, dir=both];
    next -> third [arrowhead=vee, arrowtail=dot, dir=both];
    second:ref:c -> first [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, color=red];
}
```
```cpp
        cursor = head;
```
```graphviz
digraph linkedlist {
    rankdir=LR;
    node [shape=record, color=forestgreen]; head; cursor; next;
    node [shape=Mrecord, color=black];
    first [label="{ <data> 108 | <ref> }"];
    second [label="{ <data> 72 | <ref> }"];
    third [label="{ <data> 110 | <ref> }"];
    fourth [label="{ <data> 109 | <ref> }"];
    node [shape=none]; null [label="NULL"];

    third:ref:c -> fourth [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    fourth:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    first:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    head -> second [arrowhead=vee, arrowtail=dot, dir=both];
    next -> third [arrowhead=vee, arrowtail=dot, dir=both];
    second:ref:c -> first [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    cursor -> second [arrowhead=vee, arrowtail=dot, dir=both, color=red];
}
```
```cpp
        head = next;
    }
```
```graphviz
digraph linkedlist {
    rankdir=LR;
    node [shape=record, color=forestgreen]; head; cursor; next;
    node [shape=Mrecord, color=black];
    first [label="{ <data> 108 | <ref> }"];
    second [label="{ <data> 72 | <ref> }"];
    third [label="{ <data> 110 | <ref> }"];
    fourth [label="{ <data> 109 | <ref> }"];
    node [shape=none]; null [label="NULL"];

    third:ref:c -> fourth [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    fourth:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    first:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    next -> third [arrowhead=vee, arrowtail=dot, dir=both];
    second:ref:c -> first [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    cursor -> second [arrowhead=vee, arrowtail=dot, dir=both];
    head -> third [arrowhead=vee, arrowtail=dot, dir=both, color=red];
}
```
Round 3 ...
```graphviz
digraph linkedlist {
    rankdir=LR;
    node [shape=record, color=forestgreen]; head; cursor; next;
    node [shape=Mrecord, color=black];
    first [label="{ <data> 108 | <ref> }"];
    second [label="{ <data> 72 | <ref> }"];
    third [label="{ <data> 110 | <ref> }"];
    fourth [label="{ <data> 109 | <ref> }"];
    node [shape=none]; null [label="NULL"];

    third:ref:c -> second [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    fourth:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    first:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    next -> fourth [arrowhead=vee, arrowtail=dot, dir=both];
    second:ref:c -> first [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    cursor -> third [arrowhead=vee, arrowtail=dot, dir=both];
    head -> fourth [arrowhead=vee, arrowtail=dot, dir=both, color=red];
}
```
Round 4 ...
```graphviz
digraph linkedlist {
    rankdir=LR;
    node [shape=record, color=forestgreen]; head; cursor; next;
    node [shape=Mrecord, color=black];
    first [label="{ <data> 108 | <ref> }"];
    second [label="{ <data> 72 | <ref> }"];
    third [label="{ <data> 110 | <ref> }"];
    fourth [label="{ <data> 109 | <ref> }"];
    node [shape=none]; null [label="NULL"];

    third:ref:c -> second [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    fourth:ref:c -> third [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    first:ref:c -> null [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    next -> null [arrowhead=vee, arrowtail=dot, dir=both];
    second:ref:c -> first [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    cursor -> fourth [arrowhead=vee, arrowtail=dot, dir=both];
    head -> null [arrowhead=vee, arrowtail=dot, dir=both, color=red];
}
```
```cpp
    return cursor;
}
```

## 2. 函式 swap_pair 和 reverse 對於指標的操作方式顯然異於 add_entry 及 remove_entry，需要額外做 head = ... 的更新，請用指標的指標來改寫，並避免回傳指標

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

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

## 3. 以遞迴改寫上述的 reverse，注意，你可能因此需要建立新的函式，如 rev_recursive，隨後在 reverse 函式中呼叫 rev_recursive
```cpp
node_t *rev_recursive(node_t *node, node_t *cursor)
{
    node_t *next = node->next;
    node->next = cursor;
    return (next) ? rev_recursive(next, node) : node;
}

void reverse(node_t **head)
{
    if (*head)
        *head = rev_recursive(*head, NULL);
}
```

## 4. 針對 singly-linked list 的節點，實作 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle)，你應該儘量降低記憶體的使用量

```cpp
#include <time.h>

size_t list_size(node_t *head)
{
    size_t i = 0;
    for (; head; i++)
        head = head->next;

    return i;
}

void push_node(node_t **indirect, node_t *node)
{
    node->next = *indirect;
    *indirect = node;
}

node_t *pop_node_by_pseudo_index(node_t *pseudo, size_t index)
{
    for (; index; index--)
        pseudo = pseudo->next;

    node_t *cursor = pseudo;
    pseudo = pseudo->next;
    cursor->next = pseudo->next;
    pseudo->next = NULL;
    return pseudo;
}

void shuffle(node_t **head)
{
    size_t size = list_size(*head);
    if (size < 2)
        return;

    node_t pseudo = {.next = *head};
    *head = NULL;
    for (size_t i = size; 0 < i; i--) {
        size_t roll = rand() % i;
        push_node(head, pop_node_by_pseudo_index(&pseudo, roll));
    }
}

int main(int argc, char const *argv[])
{
    srand((unsigned) time(NULL));
    ...
    shuffle(&head);
    print_list(head);

    return 0;
}
```

## Reference
* [2020q3 第 1 週測驗題](https://hackmd.io/@sysprog/sysprog2020-quiz1)
* [Graphviz](https://graphviz.org/)
* [LeetCode: Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs)
* [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle)
