---
# System prepended metadata

title: 2023 年「資訊科技產業專案設計」作業 2

---

#  info2023-homework2

> 貢獻者: Huaxin
[21. Merge Two Sorted Lists 模擬面試錄影(漢)](https://youtu.be/_Xmne0gEV_g)

## 自評-程式部分

* 很容易在打變數名稱打錯字，需要再細心一點 
## 自評-面試過程

* 說話內容，我認為還是有點不流利，我知道這是我的缺點，我會盡可能在生活中去練習。
## 自評-嘗試改進部分 

雖然進行了兩次作業，但仍然很緊張，希望能盡快克服這一點

## 他評-嘗試改進部分

感謝大家的指教，我將改進部分整理在下面

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，我們想要將各部門名單合併並以升序表示。

🐕：這想法挺好的，那面試就到這裡。