# [21. Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/description/)
面試官: 地精-Dee-jing
面試者: 尼莫魚魚-nemo

面試官: 你好我是今天負責面試你的人，假設你正在參與一個資料處理系統的開發，這個系統需要處理大量已排序的數據。系統的任務之一是合併不同來源的數據，並且這些數據已經各自進行過排序。為了簡化並提高系統效率，我們希望在維持排序的情況下合併這些列表。現在我們希望你來設計一個函數，將兩個排序好的 list 合併成一個有序的 list 。每個節點的值範圍在 -100 到 100 之間。

面試者: 所以我會拿到兩個節點值都為整數的 list，然後我要將它們合併成一個有序的list，例如我拿到 list1 = [1,2] 、 list2 = [2,3]，我要回傳[1,2,2,3]對嗎

面試官: 沒錯，你的理解沒有問題

面試者: 那我想請問一下若其中一個 list 為空，是直接回傳另一個 list 還是需要另外做處理呢

面試官: 若有其中一個 list 為空，只須回傳另一個 list 即可

面試者: 了解，那我這裡先稍微說明一下我解題的想法，首先用遞迴比較兩個 list 的第一個節點，選擇較小的節點接入合併的 list，並將該 list 的下一個節點和另一個 list 進行下一次遞迴。例如，給定 list1 = [1, 2, 4] 和 list2 = [1, 3, 5]，我會先選擇 list1 的第一個節點 1，接著讓 list1[2, 4] 和 list2[1, 3, 5] 繼續遞迴，直到合併完成。

面試官: 聽起來沒什麼問題，那你可以開始實作了

面試者: 好的那我選用的語言是 c++，我這裡會先定義 linked list 的結構....

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1 == NULL) return list2;
        if(list2 == NULL) return list1;
        if(list1->val <= list2->val){
            list1->next = mergeTwoLists(list1->next,list2);
            return list1;
        }
        else{
            list2->next = mergeTwoLists(list1,list2->next);
            return list2;
        }
    }
};

面試官: 那我想請問一下，由於你本題是使用到遞迴，會浪費到不少空間，請問你可以提出其他方法來減少空間的使用嗎

面試者: 先前方法確實造成了空間的浪費，那我這裡想改採用 iteration 的方式來修改，避免函式的重複呼叫，應該可以減少空間的使用

面試官: 好，那你試看看

面試者: 好 ...(邊coding邊解釋)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(!list1) return list2;
        if(!list2) return list1;
        ListNode* head = list1;
        if(list1->val <= list2->val){
            list1 = list1->next;
        }
        else{
            head = list2;
            list2 = list2->next;
        }
        ListNode* curr = head;
        while(list1 && list2){
            if(list1->val <= list2->val){
                curr->next = list1;
                list1 = list1->next;
            }
            else{
                curr->next = list2;
                list2 = list2->next;
            }
            curr = curr->next;
        }
        if(list1) curr->next = list1;
        if(list2) curr->next = list2;
        return head;
    }
};

面試者: 由於合併後的 list 是透過指針在原本的 list 上進行操作，不會像遞迴每次調用都會建立新的stack，因此可以讓空間複雜度降低到O(1)

面試官: 好，明白了，今天面試就到這，感謝你的參與

## 自評
- 講話會有點卡詞
- 在介紹程式碼時，對於linked list描述較不熟悉，因此敘述方面會有點不通順或者誤用詞的情況
- 說話可以在大聲一點
# [88 Merge Sorted Array](https://leetcode.com/problems/merge-sorted-array/description/)
面試官: 尼莫魚魚-nemo
面試者: 地精-Dee-jing

面試官：你好，今天我們會討論 LeetCode 的第88題「合併兩個有序數組」。你可以先簡單描述一下這道題的要求嗎？

面試者🧔：好的，這道題要求將兩個已經排序的數組合併成一個有序數組，並且結果需要儲存在 nums1 中。這在數據合併、排序等應用中經常會用到。題目給的條件是，nums1 有足夠的空間容納合併後的結果，但其中只有 m 個有效元素，而 nums2 中有 n 個元素。我們需要將 nums2 中的所有元素合併到 nums1 中，保持兩者的排序，並且不使用額外空間。

面試官：不錯，那你會如何著手解決這道題呢？

面試者🧔：我的解法是從兩個數組的末尾開始進行比較和合併，這樣可以避免覆蓋掉 nums1 中的有效數據。具體來說，我會用到三個指針變量：

i 指向 nums1 中最後一個有效元素的位置。
j 指向 nums2 中的最後一個元素。
k 指向 nums1 最後一個位置，這將是合併後放置結果的位置。

然後，我會從後往前比較 nums1[i] 和 nums2[j]，將較大的值放在 nums1[k]，並移動相應的指針。這樣可以確保在不覆蓋有效數據的前提下進行合併。

面試官：那能展示一下具體的程式碼嗎？

#include <stdio.h>

void merge(int* nums1, int m, int* nums2, int n) {
    int i = m - 1;  // 指向 nums1 的最後一個有效元素
    int j = n - 1;  // 指向 nums2 的最後一個元素
    int k = m + n - 1;  // 最終合併位置

    while (i >= 0 && j >= 0) {
        if (nums1[i] > nums2[j]) {
            nums1[k--] = nums1[i--];
        } else {
            nums1[k--] = nums2[j--];
        }
    }

    // 將剩餘的 nums2 元素拷貝到 nums1 中
    while (j >= 0) {
        nums1[k--] = nums2[j--];
    }
}

面試官：很好，請解釋一下這段程式碼的邏輯吧。

面試者🧔：當然。在這裡，i 和 j 分別指向 nums1 和 nums2 的最後一個有效元素位置，k 是合併結果儲存的目標位置。接下來的流程是：

比較 nums1[i] 和 nums2[j] 的大小，將較大的元素放到 nums1[k]，然後向前移動指針 k。
重複這個過程直到其中一個數組被合併完。
如果 nums2 中還有剩餘元素，繼續將它們複製到 nums1 開頭，這樣可以確保最終結果有序。
這個方法能避免覆蓋 nums1 中的有效元素，同時實現從後往前合併的排序過程。

面試官：你對這段程式碼的時間和空間複雜度有什麼看法？

面試者🧔：這段程式碼的時間複雜度是 O(m + n)，因為需要遍歷 nums1 和 nums2 中的所有元素才能完成合併。在空間複雜度方面，這個方法是原地合併的，直接在 nums1 上操作，因此空間複雜度是 O(1)，沒有額外的空間需求。

面試官：很好，這是最優解嗎？還有其他可以優化的地方嗎？

面試者🧔：在這道題的條件下，這已經是最優解法。由於需要從後往前合併來避免覆蓋，所以在不使用額外空間的情況下，我認為這是最理想的方式。時間複雜度 O(m + n) 也是最小的，因為我們至少需要檢查所有元素。

面試官：很好的解釋。最後，你能總結一下這道題的關鍵點嗎？

面試者🧔：好的。這道題的關鍵在於利用數組已經排序的特性，從後往前合併，這樣可以避免覆蓋掉 nums1 中的有效數據。使用三個指針從末尾進行比較，確保 O(m + n) 的時間複雜度，並且保持 O(1) 的空間複雜度。

面試官：非常好，今天的表現很不錯，謝謝你！

面試者🧔：謝謝您的指導！

## 自評

- 未將題目包裝成實際可應用的例子，不應該直接說他是leetcode的哪道題
- 對話擬稿有點不自然
- 應該是由面試官出題，而不是反而讓面試者去解釋題目