# 2019q3 Homework4 (quiz4)

contributed by < `uccuser159` >

### 測驗 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;
}

請補完程式碼。

==思考==

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

由上面程式可知，left 與 right 會不斷經過遞迴將 linked list 做切割，為了要比較大小，`left = sort(left)`用來抓出第一個元素，將`left->next = NULL`。


利用 `sort(right)` 遞迴到最後的部分，直到 `right->next == NULL`，所以 `sort(right)` 最後指向 3 這個 node，再一路遞迴 `start` 回去。


利用 `*merge` 來建立 node 之間的連結

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;
}

以此範例
* `if (!merge)` 為第一次要做 merge 的元素，所以 LL4 為`start=merge=right`
* 接著要讓 `right` 更新跑下一個 node 來判定與`left`之間的大小，LL6 為`right=right->next`
* 因為`right==NULL`或是`left`與`right`都有指向某 node 但`left->data`比較小（此處範例為`right==NULL`的狀況），則`left` 指向 `merge` ，因為不是第一次做 merge 的元素，跑到 else 判斷，所以 LL2 為 `merge->next = left` (因為有`start=merge`的操作)

相反的狀況可以推回 LL1 為 `start=merge=left`；LL3 為 `left=left->next`；LL5 為`merge->next = right`

* 延伸問題

:::warning
說好的進度呢？
:::