# [2020q1](http://wiki.csie.ncku.edu.tw/linux/schedule) 第 1 週測驗題
###### tags: `linux2020`

:::info
目的: 檢驗學員對 **[linked list](https://hackmd.io/s/SkE33UTHf)** 的認知
:::

==[作答表單](https://docs.google.com/forms/d/e/1FAIpQLSf2ujBrZ87K_cN-iFEziq2FR44kt8XlCkB2x3aZx7NehUDtNg/viewform)==
* [參考題解1](https://hackmd.io/@Ryspon/HJVH8B0XU)
* [參考題解2](https://hackmd.io/@chses9440611/Sy5gwE37I)

---

### 測驗 `1`

考慮一個單向 linked list:

typedef struct __list {
    int data;
    struct __list *next;
} list;

在不存在環狀結構的狀況下，以下函式能夠對 linked list 元素從小到大排序:

list *sort(list *start) {
    if (!start || !start->next)
        return start;
    list *left = start;
    list *right = left->next;
    LL0;

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

    for (list *merge = NULL; left || right; ) {
        if (!right || (left && left->data < right->data)) {
            if (!merge) {
                LL1;
            } else {
                LL2;
                merge = merge->next;
            }
            LL3;
        } else {
            if (!merge) {
                LL4;
            } else {
                LL5;
                merge = merge->next;
            }
            LL6;
        }
    }
    return start;
}

請補完程式碼。

==作答區==

LL0 = ?
* `(a)` `left->next = NULL`
* `(b)` `right->next = NULL`
* `(c)` `left = left->next`
* `(d)` `left = right->next`

LL1 = ?
* `(a)` `start = left`
* `(b)` `start = right`
* `(c)` `merge = left`
* `(d)` `merge = right`
* `(e)` `start = merge = left`
* `(f)` `start = merge = right`

LL2 = ?
* `(a)` `merge->next = left`
* `(b)` `merge->next = right`

LL3 = ?
* `(a)` `left = left->next`
* `(b)` `right = right->next`
* `(c)` `left = right->next`
* `(d)` `right = left->next`

LL4 = ?
* `(a)` `start = left`
* `(b)` `start = right`
* `(c)` `merge = left`
* `(d)` `merge = right`
* `(e)` `start = merge = left`
* `(f)` `start = merge = right`

LL5 = ?
* `(a)` `merge->next = left`
* `(b)` `merge->next = right`

LL6 = ?
* `(a)` `left = left->next`
* `(b)` `right = right->next`
* `(c)` `left = right->next`
* `(d)` `right = left->next`

:::success
延伸問題:
1. 解釋上述程式運作原理;
2. 指出程式改進空間，特別是考慮到 [Optimizing merge sort](https://en.wikipedia.org/wiki/Merge_sort#Optimizing_merge_sort);
3. 將上述 singly-linked list 擴充為 circular doubly-linked list 並重新實作對應的 `sort`;
4. 依循 Linux 核心 [include/linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 程式碼的方式，改寫上述排序程式;
5. 嘗試將原本遞迴的程式改寫為 iterative 版本;
:::

---