# 2019q3 第 4 週測驗題 :::info 目的: 檢驗學員對 linked list 的認知 ::: --- ### 測驗 `1` 考慮一個單向 linked list: ```cpp typedef struct __list { int data; struct __list *next; } list; ``` 在不存在環狀結構的狀況下，以下函式能夠對 linked list 元素從小到大排序: ```cpp 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 版本; 6. 將 [2019q1 第 3 週測驗題 (下)](https://hackmd.io/@sysprog/SkrVSKiU4) 提及的 XOR linked list 列入考量，也實作對應的排序程式，並比較效能和記憶體開銷; 7. 比照 [List Sort](https://arxiv.org/pdf/1310.7890.pdf) 的手法來分析前述程式 (含擴充版本) 的效能表現; ::: ---