# 2025q1 Homework2 (quiz1+2)
## Q1 測驗

### `list_insert_before`
先考量鏈結串列：

#include <stddef.h>
typedef struct list_item {
    int value;
    struct list_item *next;
} list_item_t;

typedef struct {
    struct list_item *head;
} list_t;

有兩個結構體分別為 `list_item_t` 以及 `list_t`，而 `list_insert_before` 這個函式如下：

static inline void list_insert_before(list *l, list_item_t *before, \
list_item_t *item)
{
    list_item **p;
    for (p = &(l->head); *p != before; p = &(*p)->next)
        ;
    *p = item;
    item->next = before;
}

他需要帶入一個 `list` 以及指向 `before` 與指向 `item` 的結構體 `list_item_t`，而函式的功能是將 `item` 插入 `before` 之前，考量以下三種情境：
1. `before` 指向鏈結的頭部，則 `item` 插入到頭部之前
2. `before` 為 `NULL`，則 `item` 加到鏈結的尾端
3. `before` 不存在在鏈結當中，則視為未定義行為

首先，會先建立 N 個 `list_item_t` 的結構體 `items` ，以及 `list_t` 的結構體 `l`，並且對鏈結串列初始化，每當 `items` 初始化的數量增加，後面 `items` 的 `value` 就會比前面再多加 1。

#define N 1000

static list_item_t items[N];
static list_t l;

static list_t *list_reset(void)
{
    for (size_t i = 0; i < N; i++) {
        items[i].value = i;
        items[i].next = NULL;
    }
    l.head = NULL;
    return &l;
}

當我們執行 `test_list` 時，會進行 `list_insert_before` 命令，並且分別對插入到頭部和插入到尾端進行測試：
插入到頭部：

for (size_t i = 0; i < N; i++)
        list_insert_before(&l, l.head, &items[i]);

size_t k = N - 1;
list_item_t *cur = l.head;
while (cur) {
    my_assert(cur->value == k, "Unexpected list item value");
    k--;
    cur = cur->next;
    }

插入到尾端：

for (size_t i = 0; i < N; i++)
        list_insert_before(&l, NULL, &items[i]);

k = 0;
cur = l.head;
while (cur) {
    my_assert(cur->value == k, "Unexpected list item value");
    k++;
    cur = cur->next;
}

### 在現有的程式碼進行合併排序

list_item_t *find_middle(list_item_t *head) {
    if (!head || !head->next)
        return NULL;
    list_item_t *slow = head;
    list_item_t *fast = head->next;
    
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

list_item_t *mergeTwo(list_item_t *left, list_item_t *right) {
    list_item_t *head;
    list_item_t **ptr = &head;
    while (left && right) {
        if (left->value < right->value) {
            *ptr = left;
            left = left->next;
        } else {
            *ptr = right;
            right = right->next;
        }
        ptr = &(*ptr)->next;
    }
    *ptr = left ? left : right;
    return head;
}

list_item_t *mergeSort(list_item_t *head) {
    if (!head || !head->next)
        return head;
    list_item_t *mid = find_middle(head);
    list_item_t *left = head;
    list_item_t *right = mid->next;
    mid->next = NULL;
    
    list_item_t *left_sorted = mergeSort(left);
    list_item_t *right_sorted = mergeSort(right);
    list_item_t *merged = mergeTwo(left_sorted, right_sorted);

    
    
    return merged;
}

## Q2 測驗

if ((*node_ptr)->l && (*node_ptr)->r) {

    block_t **pred_ptr = &(*node_ptr)->l;
    while ((*pred_ptr)->r)
        pred_ptr = &(*pred_ptr)->r;