###### tags: `Linux核心`
# 2020q3 Homework1 (quiz1)
contributed by < `heysun0728` >

[詳細題目內容點此](https://hackmd.io/@sysprog/sysprog2020-quiz1)

## 1. 解釋程式運作原理
:::info
To do
:::

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

* \#5~\#7：為新建立的 node 分配空間，並設定 `value` 及 `next` 值
* `assert(new_node);`
* 在 [ISO/IEC 9899 (a.k.a C99 Standard)](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf) 中 7.2.1.1 內可查閱到 assert macro 功能
* 此處是為確保 `malloc` 能正確為 `new_node` 分配到空間
* \#10~#12：在 while 迴圈中 indirect 會從頭開始一一指向 list 中每一個 node，直到走到 list 尾端才會結束。此時 #12 會將 new_node 插入至最後一個 node 的 next 指標所指向之處。

> 函數作用：將 *head 指向的 list 尾端加入一個值為 new_value 的 new node

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

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

## 2. 用指標的指標改寫 `swap_pair` 和 `reverse`
函式 `swap_pair` 和 `reverse` 需要額外做 `head = ...` 的更新，請用指標的指標來改寫，並避免回傳指標。

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

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

int main(int argc, char const *argv[])
{
    ...
    swap_pair(&head);
    print_list(head);

    reverse(&head);
    print_list(head);
}

## 3. 撰寫遞迴版 `reverse`
以遞迴改寫上述的 reverse。

void rev_recursive(node_t **head, node_t *cursor) {
  if (!(*head)) {
    *head = cursor;
    return;
  }
  node_t *next = (*head)->next;
  (*head)->next = cursor;
  cursor = *head;
  *head = next;
  rev_recursive(head, cursor);
}

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

## 4. 實做 Fisher-Yates shuffle
針對 singly-linked list 的節點，實作 Fisher–Yates shuffle，你應該儘量降低記憶體的使用量。
:::info
To do
:::