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

###### tags: `sysprog2020`, `quiz`

## :memo: Table of Contents
[TOC]

---

## :page_facing_up: 題目
:::spoiler
考慮一個單向 linked list，其結構定義為:

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`
對應的程式碼如下:

#include <stdio.h>
#include <stdlib.h>
#include <assert.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
}

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; node = &(*node)->next->next) { // BB1
        node_t *tmp = *node;
        *node = (*node)->next; // 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;
        head->next = cursor; // CCC
        cursor = head; // 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;
}

參考執行輸出: (第 1 行是換行符號)

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

請補完程式碼。

:::
---
## 程式運作原理
以 `add_entry()`, `find_entry()`, `remove_entry()`, `swap_pair()`, `reverse()`, `print_list()` 等六個 function 組成

----

### add_entry() function 說明

void add_entry(node_t **head, int new_value)
{
    // 使用雙重指標，indirect 位址跟 head 位址相同
    node_t **indirect = head; 
    
    // 新增節點 new_node，並依據 Parameter in assign value
    node_t *new_node = malloc(sizeof(node_t));
    new_node->value = new_value;
    new_node->next = NULL;
    
    // 使用 assert Macro 判斷是否 malloc 成功 
    assert(new_node);
    // 要將新建的 node 連上 linked list，*indirect 代表連出去的節點
    // 若 *indirect == NULL，代表到了 linked list 的尾端
    // 若 *indirect = NULL，則使用 "&" 得到 *indirect 的值，也就是 node
    // 再指向 next，得到下一個 node
    while (*indirect)
        indirect = &(*indirect)->next;
    // 將 new_node 接續上 linked list 的尾端
    *indirect = new_node;
}
int main()
{
    node_t *head = NULL;
    add_entry(&head, 72);
    add_entry(&head, 101);
    add_entry(&head, 108);
    add_entry(&head, 109);
    // linked list: 72 -> 101 -> 108 -> 109
}

* assert() 是一個 Macro，而非一個 function，定義在 ISO C99 中的 <assert.h>
* 型態為：void assert( int expression )，若 expression 為 0，則印出 error message，並執行 abort
### find_entry() function 說明

node_t *find_entry(node_t *head, int value)
{
    node_t *current = head;
    // 從 head 開始，若是 current != NULL 且 current->value 不等於要找的 value 值，往 next 去找
    for (; current && current->value != value; current = current->next)
        /* interate */;
    return current;
}
int main()
{
    node_t *entry = find_entry(head, 101);
}

### remove_entry() function 說明

void remove_entry(node_t **head, node_t *entry)
{
    // 將 indirect assign 成 head
    node_t **indirect = head;
    // 若 *indirect 並不等於 entry，往 next 去找
    while ((*indirect) != entry)
        indirect = &(*indirect)->next;
    // 直接更改 *indirect 成下一筆資料，這樣原先的 node 就自動不在 linked list 當中
    *indirect = entry->next;
    // 將 entry free 掉，以免發生 memory leak
    free(entry);
}
int main()
{
    entry = find_entry(head, 111);
    remove_entry(&head, entry);
}    

### swap_pair() function 說明

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

### reverse() function 說明

node_t *reverse(node_t *head)
{
    node_t *cursor = NULL;
    // 依序從 head 往下做，直到 linked list 的尾端即完成 reverse
    while (head) {
        // 新增一個 *next 節點，並 assign 成 head->next
        node_t *next = head->next;
        // 因要 reverse，所以 head->next 會倒過來變 head，所以 head->next assign 成 head
        head->next = cursor; // CCC
        cursor = head; // CCC
        // head assign 成 line 14 的 next
        head = next;
    }
    // 回傳 cursor，現在已變成 reverse 後的 head
    return cursor;
}

### print_list() function 說明

void print_list(node_t *head)
{
    // current assign 成 head，只要還沒到結尾，current 就繼續往 next 走
    for (node_t *current = head; current; current = current->next)
        printf("%d ", current->value);
    printf("\n");
}