2025 年「資訊科技產業專案設計」課程第 1 次作業

# 2025 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2025)」課程第 1 次作業 > 貢獻者: 法拉第 Faraday video 👨‍💼：interviewer 👩‍💻：interviewee ::: spoiler 作業要求以 HackMD 紀錄上述模擬面試過程的討論、程式碼、改進方案，和初步檢討自己的表現 * Repeat: 重複提問，確認自己理解原本的要求 * Examples: 針對題目條件，舉出符合的案例，不限於特例 * Approach: 說明自己打算採用的方案 * Code: 撰寫程式 * Test: 若不能實際測試，那說明驗證程式的方案 * Optimization ::: ## 模擬面試過程 ### [21. Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/description/?envType=problem-list-v2&envId=linked-list) 👨‍💼 請你用 C 語言實作一個函式，把兩個已排序的單向鏈結串列合併成一個新的排序串列。 👩‍💻 好的。那我重複一下，題目的需求是要將兩個已排序排序的鏈結串列，合併成一個新的已排序鏈結串列，這樣對吧? ==R== 👨‍💼 沒錯。 👩‍💻 沒問題。那我想詢問一下，是否有限制排序方式要用升序還是降序? 👨‍💼 沒有限制，可以自行決定。 👩‍💻 好。那我就假設輸入的兩個 list 都是升序排列，假設是 `[1,2,4]` 跟 `[1,3,4]` 好了，那輸出的 list 就會是 `[1,1,2,3,4,4]` 這樣。==E== 👩‍💻 這題我打算先比較兩個串列目前節點的值，然後把比較小的節點接到結果串列的後面，一直重複直到其中一個串列結束，再把剩下的串列直接接上去。==A== 👨‍💼 很好。那麼你可以開始寫出你的程式碼。 ==C== ```c struct ListNode { int val; struct ListNode *next; }; struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { struct ListNode *head = NULL; struct ListNode **ptr = &head; while (list1 != NULL && list2 != NULL) { if (list1->val < list2->val) { *ptr = list1; list1 = list1->next; } else { *ptr = list2; list2 = list2->next; } ptr = &(*ptr)->next; } *ptr = (list1 != NULL) ? list1 : list2; return head; } ``` 👩‍💻 接下來我舉一個例子來驗證程式碼。假設兩個串列 `1 → 3 → NULL` 及 `2 → 4 → NULL`，回傳值為 `head → 1 → 2 → 3 → 4 → NULL` ，是正確的結果。==T== 👨‍💼 很好。那時間與空間複雜度呢？ 👩‍💻 假設兩個串列長度分別是 `m` 跟 `n` ，那時間複雜度是 `O(m+n)`，因為每個節點都會走過一次。空間複雜度是 `O(1)`，因為沒有額外配置新節點，只用了一些指標。 👨‍💼 不錯。你可以用遞迴的方式寫嗎？ ==O== ```c struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) { if (l1 == NULL) return l2; if (l2 == NULL) return l1; if (l1->val < l2->val) { l1->next = mergeTwoLists(l1->next, l2); return l1; } else { l2->next = mergeTwoLists(l1, l2->next); return l2; } } ``` 👨‍💼 這個版本有甚麼風險嗎? 👩‍💻 但如果串列非常長，遞迴版本會一直呼叫自己的函式，就會有 stack overflow 的風險。這時候迭代版本會比較安全。 👨‍💼 很好，今天的面試就到這裡。 ### [83. Remove Duplicates from Sorted List](https://leetcode.com/problems/remove-duplicates-from-sorted-list/description/?envType=problem-list-v2&envId=linked-list) 👨‍💼 You are given a sorted linked list. Please write a function to delete all duplicates such that each element appears only once. 👩‍💻 So, I’m given a sorted linked list, and I need to remove the duplicates so that each value appears only once. Then I return the updated list. Is that correct? ==R== 👨‍💼 Yes, that’s correct. 👩‍💻 Okay. Let me give a quick example. Suppose the list is `1 → 1 → 2 → 3 → 3`, After removing duplicates, it should become `1 → 2 → 3`. ==E== 👨‍💼 Yes, that’s correct. 👩‍💻 Okay. Since the list is sorted, all duplicates will be next to each other. My idea is to use a pointer-to-pointer that initially points to the head of the list. I’ll keep moving through the list, and for each node I just check if the next node has the same value. If it does, I simply skip the duplicate by reconnecting the pointer. If not, I move forward to the next node. By doing this until the end of the list, I make sure that every value only appears once, and then I return the head of the updated list. ==A== 👨‍💼 Good. You can start implementing it. ==C== ```c struct ListNode { int val; struct ListNode *next; }; struct ListNode* deleteDuplicates(struct ListNode* head) { struct ListNode **ptr = &head; while (*ptr != NULL && (*ptr)->next != NULL) { if ((*ptr)->next->val == (*ptr)->val) { (*ptr)->next = (*ptr)->next->next; } else { ptr = &(*ptr)->next; } } return head; } ``` 👨‍💼 Nice. Why do you use a pointer-to-pointer here instead of just a normal pointer? 👩‍💻 Because using a double pointer makes it easy to handle the head node uniformly. For example, if duplicates occur at the beginning, I don’t need a separate condition for the head. I can always update the pointer that leads to the current node, whether it’s head or some next field. 👨‍💼 Good point. Can you explain with an example? 👩‍💻 Sure. Suppose the list is `1 → 1 → 2 → 3`, after processing, the result is `1 → 2 → 3 → NULL`. And that’s the correct answer. ==T== 👨‍💼 Great. What’s the time and space complexity? 👩‍💻 Time complexity: `O(n)`, because we visit each node at most once. Space complexity: `O(1)`, since we only use a few pointers, no extra memory. 👨‍💼 What if the list is not sorted? Will your solution still work? 👩‍💻 No, this solution only works for sorted lists, because it assumes duplicates are always next to each other. If the list is unsorted, we’d need a different approach, such as using a hash set to track values we’ve seen. ==O== 👨‍💼 Great answer. That’s all for this question. ### [142. Linked List Cycle II](https://leetcode.com/problems/linked-list-cycle-ii/description/?envType=problem-list-v2&envId=linked-list) 👨‍💼 請找出鏈結串列中的循環，如果有循環就回傳循環的起點，沒有就回傳 NULL。 👩‍💻 好的，。題目的需求是：輸入一個單向鏈結串列。那如果有循環，就回傳循環的起點節點；如果沒有，就回傳 `NULL`。請問我的理解是正確的嗎? ==R== 👨‍💼 沒錯，你的理解沒問題。 👩‍💻 假設串列是：3 → 2 → 0 → -4，-4 指回節點 2，那就要回傳2。假設串列是：1 → 2 → 3，就要回傳NULL。 ==E== 👩‍💻 我打算用快慢指標法來解。思路是用兩個指標：`slow` 一次走一步，`fast` 一次走兩步。如果有循環，`fast` 和 `slow` 一定會在某個點相遇；那要如何找到相遇的點，透過一個推導得知，從 `slow` 最後的所在節點，以及 `head` 節點，往前各走相同的步數，相遇的地方就會是循環的起始節點。 ==A== 👨‍💼 好，那請你開始時做程式碼。==C== ```c struct ListNode { int val; struct ListNode *next; }; struct ListNode *detectCycle(struct ListNode *head) { struct ListNode *fast = head; struct ListNode *slow = head; while (fast != NULL && fast->next != NULL) { fast = fast->next->next; slow = slow->next; if (fast == slow) { while (head != slow) { head = head->next; slow = slow->next; } return head; } } return NULL; } ``` 👩‍💻 我接下來舉個例子來驗證我的程式碼。假設串列是 `3 → 2 → 0 → -4`，`-4` 指回節點 `2`，形成環。`slow` 每次走一步，`fast` 每次走兩步。最終兩個指標在 `-4` 相遇，然後從 `head` 和 `-4` 各走一步，再相遇時就是節點 `2`，這就是環的起點。==T== 👨‍💼 很好，你有考慮到 `head` 是 `NULL` 或只有一個節點的情況嗎？ 👩‍💻 有的，如果 `head` 是 `NULL`，迴圈條件就不會進入，直接回傳 `NULL`。單節點也是同理。 👨‍💼 如果用 hash set 來解可以嗎？會不會比較優化? ==O== 👩‍💻 可以。做法是遍歷鏈結串列，每個節點存到 hash set，如果碰到已經存在的節點，就表示環的起點是該節點；遍歷完沒重複就回傳 NULL。但這個做法需要額外的空間來存遇到的節點的地址，所以空間複雜度會比較高，因此不會比較優化。 👨‍💼 很好，你講得很完整。那今天的面試就到這裡。 ## 初步檢討 1. 空白太多，要保持編寫程式邊講話。 2. 講解內容多為程式碼照念，儘量改為表達含意。 3. Hash set 版本未實作。