---
title: 2022 年「資訊科技產業專案設計」HW2
tags: INFO2022
---

# 2022 年「資訊科技產業專案設計」HW2

## 其他同學第一次面試檢討

- [起司堡-cheeseburger](https://hackmd.io/@sysprog/Bkdiazbzs) Contains Duplicate
- 雖然展示對hash table的理解，但對題目本身比較忽略。
- [傑倫米-Jeremy](https://hackmd.io/@sysprog/SkM3qFxMo) Palindrome Partitioning
- 主要檢討了畫面和聲音。
- [鞋墊-Shoe](https://hackmd.io/@sysprog/S1snp6U-o) Pow(x, n)
- 實際寫code前，interviewee配合文字說明做的很詳細，很容易理解interviewee的思路。
- [店到電-shopee](https://hackmd.io/@sysprog/B1VDX5lfs) Add Two Numbers
- 因為大部分同學都有自己檢討到，所以沒有寫很多。
- [魏昇芷-tissue](https://hackmd.io/@sysprog/HkEWKtlzs) Add Two Numbers
- 因為我自己程式能力不算很好，看不出很多問題，所以後面看了幾個同學跟我都有做的Add Two Numbers，覺得這個同學整體做得很好，很值得參考。

## [第二次作業](https://youtu.be/0MVf5yMEiNY)

🐱：你好，我想請你將兩個已排序的linked list結合成一個同樣也是排序的linked list。那排序都是由小至大。具體你可以參考文件上的範例。
🐶：好的，請問排序時若list1與list2的值相同時，兩者有優先順序嗎？
🐱：沒有。
🐶：那會有兩個輸入皆為空的情況嗎？
🐱：會，如果兩個輸入都是空，那傳回的值也同樣設為空。
🐶：好的,那我想如果輸入為1-3-5和2-4-6那結果應該傳回1-2-3-4-5-6，對吧？
🐱：對的。
🐶：好，那我想我理解了。那我會想要用兩個指標依序走訪，像是剛剛提到的135 246，一開始兩個都會指著開頭，那因為判斷1<2，所以將1加入，然後第一個指標往後指。那這樣應該就可以從小到大，依序走訪兩個linked list。
🐱：很好，你可以開始實作了。

🐶：首先創一個空白的節點，然後用一個指標指linked list目前最尾端的位址。然後因為我要比兩個node的值，必須兩者皆非null，所以我這邊用while兩者皆非空。如果list1的值小於list2，那目前(結果)的linked list結尾就指向list1(的目前節點)，然後list1往後走。那list2的值比較小時，也做相同的事。那因為剛剛說沒有優先順序，所以就想成兩者相等時直接等同list2較小就好。然後指到最新的尾端。那因為最後其中一個list會較快結束，此時令尾端加上非null的那邊。然後就結束，可以回傳head的next了。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
       ListNode head(0);
       ListNode* t = &head;
       while(list1 && list2){
           if (list1->val < list2->val){
              t->next = list1;
              list1 = list1->next;
           }
           else{
              t->next = list2;
              list2 = list2->next;
           }
           t = t->next;
       }
       t->next = list1 ? list1 : list2;
       return head.next;
    }
};

🐶：那這個方法的時間複雜度,會是O(n+m)，n和m是兩個input的長度，因為此程式while部分最多就是每個節點各經過一次。那空間複雜度以此方法來說是O(1),因為我只有創建新的head與儲存位址的指標。
🐱：那你覺得這題有什麼實際應用的價值嗎？
🐶：linux的kernel中，有一個list_sort的function，是將一個長度n的list做排序，會將長度n的list視為n個sublist，每次對兩個sublist做此題的merge，然後就會一個一個減少，最後就可以得到一個排序好的list.