# 2020q1 Homework3 (quiz3)
contributed by < `jwang0306` >

> [作業要求](https://hackmd.io/@sysprog/rJXs6hrHU)

## 測驗一： XOR Linked List
題目的敘述有一段 `insert_node` 的程式碼：

void insert_node(list **l, int d) {
    list *tmp = malloc(sizeof(list));
    tmp->data = d;

    if (!(*l)) {
        tmp->addr = NULL;
    } else {
        (*l)->addr = XOR(tmp, (*l)->addr);
        tmp->addr = *l;
    }
    *l = tmp;
}

上課時我被問到這個是插在 list 的頭還是尾巴，印象中我只有回答其中一個，但是後來仔細思忖，答案是頭尾都可以，端看參數 `list **l` 給的是頭還是尾。

已知 XOR 的運算特性：
* $A \oplus 0 = A$
* $(A \oplus B) \oplus B = A$

走訪 list 的方式為當前節點與前一個節點取 XOR ，假設節點 1, 2, 3, 4 ，當前節點在 1 ：

       1    2    3    4
data  HAT  CAT  EAT  BAT

- 要走到 2 的話，就是 `link(1) XOR 0` = `(0 XOR 2) XOR 0` = `2` （根據特性二）
- 要插入一個 `FAT` 到尾巴的話，如果 list 為空，直接 `*l = tmp` ，前後都沒人因此 `addr` 為 `NULL`
- 如果 list 不為空
- 我們希望插入後的 l 其位置為 `link(4) XOR 0` ，因此取 `XOR(tmp, (*l)->addr);` ， `0 XOR link(4)` = `link(4)` （根據特性一），然後將其更新為 `l` 的當前 `addr` ，這樣就清出了一個新的空間
- 最後再把 `tmp` 放進去
- 插在頭也是一樣的

## 解釋下方 XOR linked list 排序實作的原理

list *sort(list *start)
{
    if (!start || !start->addr)
        return start;

    /* split the list recursively */
    list *left = start, *right = start->addr;
    left->addr = NULL;
    right->addr = XOR(right->addr, left);

    left = sort(left);
    right = sort(right);

    /* merge the list recursively */
    for (list *merge = NULL; left || right;) {
        if (!right || (left && left->data < right->data)) {
            list *next = left->addr;
            if (next)
                next->addr = XOR(left, next->addr);

            if (!merge) {
                start = merge = left;
                merge->addr = NULL;
            } else {
                merge->addr = XOR(merge->addr, left);
                left->addr = merge;
                merge = left;
            }
            left = next;
        } else {
            list *next = right->addr;
            if (next)
                next->addr = XOR(right, next->addr);

            if (!merge) {
                start = merge = right;
                merge->addr = merge;
            } else {
                merge->addr = XOR(merge->addr, right);
                right->addr = RR2;
                merge = right;
            }
            right = next;
        }
    }

    return start;
}

上述的 XOR linked-list 用了類似 merge sort 的手法，不斷地切割 list ，最後拼裝起來：
- 先讓 `next` 走向下一個節點
- 首次進入迴圈， `merge` 為空，因此根據大小設定為 `left` 或 `right` ，`addr` 為 `NULL`
- 否則將 `left` 接上（假設為 `left` ）， 與上述走訪的概念一樣， `merge->addr = XOR(merge->addr, left);` (`merge` 就像上方 `insert_node` 的 `l`) ，並將 `left->addr` 更新為 `0 XOR mege` 也就是 `merge` （根據特性一），最後將 `left` 放進 `merge`