2025q1 Homework2 (quiz1+2)

contributed by < gg21aping >

W1 測驗題一

list_insert_before() 函式透過指標的指標 **p 直接修改鏈結關係而非僅是節點的內容。

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

透過指標的指標操作，我們可以使用統一的方式處理所有的插入場景：

1. 當 before == l->head 時，新節點插入鏈結頭部：
   • p 指向 &l->head，*p 即 l->head
   • 跳出循環條件 *p != before
   • 設定 *p = item 即 l->head = item
   • item->next 指向 before，即原先 l->head 指向的節點
2. 當 before == NULL 時，新節點插入鏈結尾部：
   • 循環會一直執行直到鏈結最末端，即 *p = NULL
   • 注意 p = &(*p)->next 是下一個指標的位址，p 依然保留指向指標的特性
   • *p = item 將尾節點的 next 指向新節點
   • item->next = before 把新節點的 next 指標指向 NULL
3. 在鏈結的中間插入新節點：
   • 循環到 *p == before
   • 透過 *p = item 讓前一個節點指向新節點
   • item->next = before 連接後續的節點

合併排序（merge sort）操作