# 2020q3 Homework1 (quiz1)
contributed by <OliveLake>

- ==[Linked list 練習題](https://hackmd.io/@sysprog/sysprog2020-quiz1)==

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

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

已知不存在 circular (環狀結構)，接下來將對該單向 linked list 進行下列操作:
#### 1.`add_entry`: 新增節點，當 linked list 沒有內容時，必須由開發者更新指向開頭的指標。因此實際得到 reference，而非 copy

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;
    /* AA1 */
    assert(new_node);
    while (*indirect)
        indirect = &(*indirect)->next;
    /* AA2 */
    *indirect=new_node;
}

assert()是用來除錯，如果參數是非零值則no action，若為零值則會終止程式。

AA1:選擇`assert(new_node)`是為了確定malloc有成功要到正確的記憶體

AA2:選擇`*indirect=new_node`，將indirect這個指標的值設給`new_node`

#### 2.`swap_pair`:交換一對相鄰的節點，取自 [LeetCode: Swap Nodes in Pairs ](https://leetcode.com/problems/swap-nodes-in-pairs/)，給定 1->2->3->4，則該回傳 2->1->4->3

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

BB1:選擇`node = &(*node)->next->next`，因為是兩兩交換，每次都要跳兩個node
BB2:選擇`*node = (*node)->next;`，因為要對兩個node的`連接`做交換，所以是`*node`

#### 3.`reverse:`將給定的 linked list 其內節點予以反向，即 1->2->3->4，則該回傳 4->3->2->1

node_t *reverse(node_t *head)
{
    node_t *cursor = NULL;
    while (head) {
        node_t *next = head->next;
        /*CCC*/
        head->next = cursor; cursor = head;
        head = next;
    }
    return cursor;
}

CCC:選擇`head->next = cursor; cursor = head`，先宣告一個指標cursor，只要head不為NULL，就宣告一個指標next指向head的next，再將head的next指向cursor，cursor指向head，head再去指向下一個node，以實現反轉cursor的目的。