# info2023-homework2 > 貢獻者: Huaxin [21. Merge Two Sorted Lists 模擬面試錄影(漢)](https://youtu.be/cU4FUx7apEY) ## 自評-程式部分 * 很容易在打變數名稱打錯字，需要再細心一點 ## 自評-面試過程 * 說話內容，我認為還是有點不流利，我知道這是我的缺點，我會盡可能在生活中去練習。 ## 自評-嘗試改進部分 雖然進行了兩次作業，但仍然很緊張，希望能盡快克服這一點 ## 他評-嘗試改進部分 感謝大家的指教，我將改進部分整理在下面 1. 英文拼寫要再細心一點 2. 面試官，如果有指定測資可以直接寫在文件中 3. 在敘述 approach 時，可以記錄下幫助理解的文字 4. 沒有說明為何我的方法可以來解決這個問題 5. 在說明快慢指標時，應該加入數學解釋，為何可以找到 middle node 紀錄時間 : 2023/10/14 ## [21. Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/description/) 🐕：interviewer 🧑‍💻：interviewee 🐕：你好，我是今天負責幫你面試的，我們接下來有一套題目要請你解一下，這裡有 4 個 linked list ，請你嘗試進行合併，最後給我合併好的 linked list。 ``` list1 = [1,3,5] list2 = [2,3,7] list3 = [1,2,3] list4 = [1,6,17] ``` ### repeat 🧑‍💻：面試官您好，我重申一下您剛剛提的問題，目前有 4 個 linked list，然後進行合併，返回合併好的 linked list，對嗎 🐕：對，這 4 個 linked list 的節點數目範圍落在，0 到 300 個。節點數值範圍為 -200 到 ＋200 ### example 🧑‍💻：好，那我根據您提供的 linked list ，最後我會得到[1,1,1,2,2,3,3,3,5,6,7,17] 這樣的結果 🐕：沒錯，你的理解是正確的。 ### approach 🧑‍💻：我想先嘗試寫出一個函數，該函數會一次處理 2 個 linked list ，然後我想將 4 個 linked list 先合併成 2 個 linked list ，最後再合併成一個 linked list。 首先對該函數演算法進行說明，他的輸入是 2 個 linked list，我們可以先宣告 2 個指標分別指向 list 的 head，並宣告一個 ptr 指標存放著合併完的節點，接下來我可以定義出幾個狀況，根據這些狀況去依序處理我們的 list，第一個是兩個 list 都存在的情況 * while loop(2 個 list 都存在) * 如果 list1 的值小於 list2,那就將 list1 的節點放入 ptr 然後 list1 前進一個節點。 * 反之，那就將 list2 的節點放入 ptr 然後 list2 前進一個節點。 第二個情況是接續著第一個情況的， * while(只有一個 list 存在的話) * 將該 list 節點放入 ptr 內 🐕：你的想法不錯，那如果節點數目範圍落在 500 至 1000，資料量變大了，你的演算法還能很好的應對嗎。 🧑‍💻：可以，但是當面對大資料的合併時，所需要的空間複雜度也會隨之增加，而時間複雜度的部分為 O(2*(n+m))，在 4 個變 2 個 linked list 需要 O(2*(n+m))，在 2 變 1 時也需要 O(n+m)，總共是 O(3*(n+m))。 🐕：這個想法蠻有意思，你試著寫看看 ### code 🧑‍💻： ```c++= #include <iostream> // 定义链表节点结构 struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; // 合并两个有序链表的函数 ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode dummy(0); ListNode* curr = &dummy; // 當兩個 linked list 都存在時 while (list1 && list2) { if (list1->val < list2->val) { // 較小的節點放入 curr curr->next = list1; list1 = list1->next; } else { curr->next = list2; list2 = list2->next; } curr = curr->next; } // 當只有一個 linked list 存在時 while (list1) { curr->next = list1;// 把該 linked list 放入 curr list1 = list1->next; curr = curr->next; } // 當只有一個 linked list 存在時 while (list2) { curr->next = list2;// 把該 linked list 放入 curr list2 = list2->next; curr = curr->next; } return dummy.next; } int main() { // 建立 linked list ListNode* list1 = new ListNode(1); list1->next = new ListNode(3); list1->next->next = new ListNode(5); ListNode* list2 = new ListNode(2); list2->next = new ListNode(3); list2->next->next = new ListNode(7); ListNode* list3 = new ListNode(1); list3->next = new ListNode(2); list3->next->next = new ListNode(3); ListNode* list4 = new ListNode(1); list4->next = new ListNode(6); list4->next->next = new ListNode(17); // 合併 linked list ListNode* L = mergeTwoLists(list1, list2); ListNode* R = mergeTwoLists(list3, list4); ListNode* result = mergeTwoLists(L, R); // 输出合併后的 linked list ListNode* current = result; while (current) { std::cout << current->val << " -> "; current = current->next; } std::cout << "nullptr" << std::endl; return 0; } ``` 我們實作合併函數，先宣告一個 dummy 節點，並用一個 curr 指標指向 dummy 節點，當 list1 和 list2 都存在時，我們便去比較兩個 list 的當前節點大小，比較小的那一節點便會由 curr 指標的 next 所指向，接著擁有比較小節點的 list 往下一個節點前進，curr也是。 當剩其中一個 list 存在，我們就進入 while loop ，將該 list 中剩餘的節點轉移至 curr 指標。 然後後續將 linked list 放入函數中，得到兩個 linked list ，再丟入函數中，得當最終的 linked list。 ### test 🧑‍💻：我們舉以下例子做說明 list1 = [1,3,5] list2 = [2,3,7] list3 = [1,2,3] list4 = [1,6,17] 先同時針對 list1 和 list2 以及 list3 和 list4 分別進行合併，以 list1 和 list2 進行說明，當 node 1 和 node 2 比較，node 1 較小，於是便將 node 1 放入 L = [1]，後續依此類推可以得到，L = [1,2,3,3,5,7]，而 R = [1,1,2,3,6,17]，接著再合併一次，得到 result = [1,1,1,2,2,3,3,3,5,6,7,17] 🐕：不錯，那我再考考你，我們這個演算法可以用來解決生活中的什麼問題？ 🧑‍💻：假設公司各部門員工的年終獎金表示成升序的 linked list，我們想要將各部門名單合併並以升序表示。 🐕：這想法挺好的，那面試就到這裡。 ## 第四次作業 - 他評01 ### Interviewer - [ ] 優點 - 有針對題目的應用額外提問，很棒 - [ ] 可改進之處 - [0:14](https://youtu.be/cU4FUx7apEY?feature=shared&t=14) 影片中說在 Word 中會提供測資，但畫面中沒看到任何的測資 - [0:28](https://youtu.be/cU4FUx7apEY?feature=shared&t=28) 本課程作業有要求使用台灣科技用語，return 應該說「回傳」而非「返回」 ### Interviewee - [ ] 優點 - 描述演算法很仔細清晰，有同時撰寫虛擬碼協助理解 - 有先針對方法和面試官進行討論再實作，避免實作的方向與面試官的期待不符，很好 - [ ] 可改進之處 - [0:41](https://youtu.be/cU4FUx7apEY?feature=shared&t=42) 應該先說明輸入的資料，而不是直接說輸出的結果，不然螢幕上沒有顯示，也無法判斷是否真的正確 - [4:45](https://youtu.be/cU4FUx7apEY?feature=shared&t=295) 說明時間複雜度時，應該要先說明 $n$ 和 $m$ 分別代表兩個 linked lists 所含的元素個數，再說明時間複雜度為 $O(3\times(n+m))$ - 請想辦法關閉自動句首大寫的功能，或使用不會自動大寫的編輯器來撰寫程式，因為大部分程式語言會視大小寫為不同的 token (case sesitive)