---
tags: info2022-homework
---
# 資訊科技產業專案設計 作業2
contributed by <`魏昇芷 - tissue`>

## 自我 Review 與學習
* 觀看其他同學的影片時發現如果面試官只是把題目順順的唸過去甚至沒有舉例的話，其實很難讓面試者理解題目再幹麻，影片中面試者能理解是因為面試者早已熟悉題目，但作為不熟悉題目的旁人聽，很難理解題目的本意，所以面試官應該更完整的呈現題目。
* 觀看其他同學的影片時發現如果只是把題目順順的寫過去然後驗證答案的正確性，這樣會讓整個面試過程顯的單調，如果題目又是 easy 難度的，很難看出面試者的實力。因此，面試官如果沒有延伸的話，面試者應該要提及一些與這個題目應用相關的經驗，進而呈現自己實力。
* 有一些經典的題目可能再現實中的情形是會應用到的，但認真去思考的時候卻很難想出一個應用情境來說明，透過這次檢討他人的影片，我覺得自己以後寫完 Leetcode 後，應該好好思考這個題目的真實應用場景，而非一直執著於用更快或更省空間的方法去解題。

## [21. Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/)
> 😈: Interviewer
> 😬: Interviewee
* 😈: 嗨，你好，非常感謝你來參加我們次的面試，我是這次面試的主持人。
* 😈: OK，那今天討論一些我們在公司內部實際遇到的 issue，請你打開這份 google document，你可以看到這邊有一些員工基本資料，然後他是以 singly-linked list 來儲存的，一筆資料會存在一個 node 中，然後我們想要以員工名稱這個欄位來做排序，排序是按造字母大小由小到大排序且員工的名稱都是由大寫英文字母所組成。想請問實作這格排序你會想要哪一種排序演算法來排序。
* 😬: 我會想用 merge sort 來進行排序。
* 😈: 那可以請你簡單的說明一下 merge sort 演算法嗎?
* 😬: 好，首先 merge sort 會先將原本的 singly-linked list 切分成數個 list，直到每一個 list 都只剩下一個節點。接著，選擇相鄰的兩條 list 合併，合併時會進行比較，所以合併後的 list 會是排序好的，接著再重複將相鄰兩條 list 合併，直到合併為一條 list。
* 😈: 所以說，合併的部分就是將兩條排序好的 singly-linked list 進行合併。
* 😬: 是的。
* 😈: 好，那我想知道當你要實作合併兩條排序好的 singly-linked list 時，會怎麼樣去實作，因為我們只要用員工名稱去排序，所以我們簡化 node 的結構體，請你用這個結構體去解說。

struct List_node {
    char *name;
    struct List_node *next;
}

* 😬: 假設這兩條排序好的 singly-linked list，分別叫 list1 和 list2，重複比較 list1 和 list2 中node 所存的員工名稱，將較小的加入 list 中，然後被選中的 list 指標要往後移。 最後要檢查 list 中是否有剩餘的 node 沒有加入合併後的 list 中，如果有的話必須將剩下的 node 加入合併後的 list 中。
* 😈: 那你這個做法會額外配置其他記憶體空間嗎。
* 😬: 不會，只會宣告幾個變數。
* 😈: 好，那請你將你剛剛的想法以程式的方式來呈現， input 會是兩個 `struct List_node` 的指標分別指向兩條排序好的 list 的最前端，希望你回傳一個指標，指向合併後的 list 的最前端。
* 😬: 那我想問一下， input 可能為空指標嗎。
* 😈: 兩個 input 都可能為空指標。
* 😬:

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    if (!list1)
        return list2;
    if (!list2)
        return list1;
    struct ListNode *head = NULL, *cur = NULL, *target;
    while (list1 && list2) {
        if (strcmp(list1->name, list2->name)) {
            target = list2;
            list2 = list2->next;
        } else {
            target = list1;
            list1 = list1->next;
        }
        if (!head) {
            head = target;
            cur = head;
        } else {
            cur->next = target;
            cur = cur->next;
        }
    }
    if (list1)
        cur->next = list1;
    if (list2)
        cur->next = list2;
    return head;
}

* 😈: 好，那請你驗證這個例子

list1: "AAA" -> "BBB" -> "DDD" 
list2: "AAA" -> "CCC" -> "EEE"

* 😬:
* 😈: 好，那這邊想問你另一個問題是有些員工用到重複的名稱，你有沒有什麼想法可以利用名稱重複的特性來減少 mergeSort 的 loading?
* 😬: 我這邊想到的是改變資料的儲存方式，假設原本的 singly-linked list 是橫向的，將名稱相同的員工以縱向的 singly-linked list 串起來，這樣能讓橫向的 list 有更少的 node，mergeSort 時需要比較的 node 也會比較少。
* 😈: 那你覺得這樣的改變會影響到搜尋的效能嗎？
* 😬: 不會，因為走訪過的 node 數量是一樣的或更少。
* 😈: ok，我覺得這個 idea 沒問題，那我們今天面試就到這邊，感謝你的參與。