# [2020q2](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;
}

請補完程式碼。

==作答區==
#### 遞迴部分
閱讀for loop以前的程式碼，我們可以知道在執行至for以前，會將先遞迴至底部(return)
又if會考量到`start`是否為最後一個node(是否有下個node)，以及`left` or `right`在做為遞迴函數的參數以前已為`NULL`，這兩個情況
但我們還不知道遞迴到達底部的樣子，於是假設輸入一個node為三的linked list，並繪製出樹狀圖
完全不考量LL0的情況
<!--
插入樹狀圖
-->
從這張圖我們可以發現`right`最終會剩下一個node，到達中斷條件，但`left`不會，形成無限遞迴，推論出LL0缺少的是與left有關的程式碼，故排除 (b)
<!--
插入 acd 樹狀圖
-->
雖然`(a), (c), (d)`剩下三個選項都能使遞迴到達中斷條件，但只有(a)在遞迴至底層時將所有node拆開，形成可排序的狀態

LL0 = (a)

#### 迴圈部分
loop 條件: 如果`left`以及`right`為`NULL`則跳出迴圈
- if `!right || (left && left->data < right->data)`考慮的情況
1. `right`為`NULL`的情況
2. `left`不為`NULL` 且 `left->data`小於`right->data`
- 1和2內`!merge` 考慮的情況
- 如果`merge`為`NULL`，則執行LL1
- 如果`merge`不為`NULL`，則執行LL2並walk `merge`至下一個node
- 最後return 的為`start`，不是`merge`

考慮從小排到大及巢狀if判斷的內容，得出結論:
LL1 & LL4 不需要walk node，且是在`merge==NULL`的情況，判斷出此為`merge`的第一個node，故程式碼應為`merge=最小的node`

LL1: merge = 最小的node
LL4: merge = 最小的node

LL2 & LL5 則需要walk node，且`merge!=NULL`的情況，故程式碼應為 `merge->next = node`

LL2 = (a)
LL5 = (b)

LL3 & LL6 則是在`left`及`right`排序至`merge`後 walk node，故程式碼應為

LL3 = (a)
LL6 = (b)

考慮到最後return的為`start`，而`start`為排序好的linked list head，故LL1&LL4程式碼應改為`start = merge = 最小的node(之地址)`:

LL1 = (e)
LL4 = (f)

:::warning
- 誠實面對自己(自我檢討):
1. linked list有不熟練的地方
2. 不熟悉C語言指標，第一次看見LL1 & LL4沒有反應過來
3. 對演算法不熟(遞迴、排序以及 Divide and conquer)，影響寫題速度
4. 沒有考慮到合併中途是否能夠排序成功
:::

:::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 版本;
:::

---