# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 2
#### 查理-Charlie
#### :rabbit: : 我
#### :koala: : 面試官
[影片連結](https://youtu.be/79sx6w13hC8)

## <font color="#7C8CD4">**206.Reverse Linked List**</font>
### **模擬面試過程**
#### :koala: : 題目會給你一個指向一組Linked List的指標叫做 head，請你將這組Linked List進行反轉，並且回傳反轉後的Linked List。
#### :koala: : 請問你對題目有疑問嗎？
#### :rabbit: : 有的，我想詢問關於輸入的Linked List 的邊界條件？
#### :koala: : 輸入的Linked List 中其節點數的範圍是0~5000。
#### :rabbit: : 好的，爲了確認我對題目的理解，我想用一個例子説明。這道題讓輸入的Linked list 反轉，就是讓每個node 指向下一個node的指標反方向。
:::info
輸入： [1,3,5,7,9]
輸出： [9,7,5,3,1]
:::

#### :rabbit: : 並且在結尾的node指向的下一個node 必須給定NULL，才能確定到了linked list 的最後。
#### :rabbit: :請問我對題目的理解正確嗎？
#### :koala: : 正確，你可以開始寫你的程式了。
#### :rabbit: : 在寫程式之前，我想先講一下我的想法。
#### :rabbit: : 首先，我想到的是使用遞迴法來做這道題。我會將除了第一個節點的其他節點全部反轉，再接上原先的第一個節點，再接上NULL。

class Solution {
public:
    struct ListNode* reverseList(ListNode* head) {
        if(head == NULL || head->next == NULL){
            return head;
        }
        struct ListNode* prev = NULL;
        struct ListNode* newhead = reverseList(head->next);
        head->next->next = head;
        head->next = prev;
 
        return newhead;
    
    }
};

#### :rabbit: : 使用這個方法的空間複雜度為O(n)，時間複雜度也是O(n)。
#### :koala: : 除了用遞迴的方法之外，你覺得你還能用更好的方法解決這道題嗎?
#### :rabbit: : 第二種方法我想到的是使用迭代法來做這道題。我會先宣告 3 個 node 指標：newhead、cur、next。cur 指向我們當前需要反向的 node，而 newhead 則是指向上一個反向完的 node，至於 next 則是先指向當前 node 在反向前所指向的下一個 node。

class Solution {
public:
    struct ListNode* reverseList(ListNode* head) {
        
        struct ListNode* newhead = NULL;
        struct ListNode* curr = head;
        while (curr != NULL){
            struct ListNode* next = curr->next;
            curr->next = newhead;
            newhead = curr;
            curr = next;
        }
        return newhead;

    }
};

#### :rabbit: : 這個方法中我只宣告了 3 個指標，所以空間複雜度為O(1)。因為需要走訪每個 node 再改變他們指向的下一個的指標，所以時間複雜度為O(n)。
#### :koala: : 好的，謝謝你的作答。那我現在改變一下題目，我依然會給你一組Linked List，請你寫出可以判斷這組Linked List 是否回文的程式。請問你有任何問題嗎?
#### :rabbit: : 有的，我想請問這組 Linked List 的邊界條件?
#### :koala: : :Linked List 中的節點數範圍為1~10000。
#### :rabbit: : 好的，爲了確認我對題目的理解，我想用一個例子説明。
:::info
輸入： [1,3,5,3,1] 輸出： true
輸入： [1,3,5,7,9] 輸出： false
:::
#### :rabbit: :請問我對題目的理解正確嗎？
#### :koala: : 正確，你可以開始寫你的程式了。
#### :rabbit: : 在寫程式之前，我想先講一下我的想法。
#### :rabbit: : 首先，我會先將Linked List反轉，接著再逐一比較反轉後的Linked List 和原先的Linked List 是否一模一樣，如此便可以知道是否為回文。

class Solution{
public:
    bool isPalindrome(ListNode* head){
        if (head == NULL||head->next == NULL)
        {
            return head;
        }
        ListNode* newhead = NULL;
        ListNode* curr = head;

        while(curr!=NULL)
        {
            ListNode *temp = new ListNode(curr->val);
            temp ->next = newhead;
            newhead = temp;
            curr = curr->next;
        }
        while(head && newhead)
        {
            if (head->val != newhead->val)
            {
                return false;
            }
            head = head->next;
            newhead = newhead->next;
        }
        return true;
    }
};

#### :rabbit: :使用這個方法的空間複雜度為O(n)，時間複雜度也是O(n)。
#### :koala: :好的，謝謝你。

---

### **模擬面試檢討**
### <font color="#7C8CD4">**自評**</font>
interviewer:
1. 口齒可以更加清晰。
interviewee:
1. 口齒可以更加清晰
2. 說話聲音再大一點
3. 一邊打程式一邊解說時，聲音會越來越小。
4. [3:12](https://www.youtube.com/watch?v=47nKdqIsUuU#t=3m12s) [4:10](https://www.youtube.com/watch?v=47nKdqIsUuU#t=4m10s)打錯字(正確: head、reverseList)，應該多練習打程式的速度和正確率

---

### <font color="#7C8CD4">**第一次作業的收穫**</font>
interviewer:
* 優點
1. 有開場白，可能會先介紹自己是哪一間公司...，先和interviewee稍微互動後才進入題目
2. 題目有做變形，延伸到一些真實情況上

interviewee:
* 優點
1. 口齒清晰，聲音自然，語速穩定
2. 解釋程式時的思路清楚

### 第四次作業 他評01
* [3:30](https://youtu.be/79sx6w13hC8?t=208)人的收音不好，音量偏小，另外像[16:17](https://)~[16:27](https://)這邊聲音都糊在一起，而且整個面試出現很多次機車、汽車經過的聲音，需要換去更安靜的房間面試、窗戶關小一點，或是找降噪方法。
* [2:03](https://youtu.be/79sx6w13hC8?t=123)、[4:06](https://youtu.be/79sx6w13hC8?t=246) reverse都拼錯字了。
* [7:07](https://youtu.be/79sx6w13hC8?t=421 )講複雜度O(n)卻忘記講為什麼，給人感覺像用背的。不過後面說明遞迴解法的複雜度時就有記得講原因，讚。
* [7:08](https://youtu.be/79sx6w13hC8?t=428 )interviewer問的是「更好」的方式，interviewee回答迭代法後卻沒有比較以上兩個方法說明為什麼迭代更好，interviewer好像也忘記自己說過要找更好的解法，直接就進入下一題。我覺得可能的回答可以說空間複雜度更低。
* [7:31](https://youtu.be/79sx6w13hC8?t=442)講的是三個「指標」，但後面code時就講成「指針」了。
* 因為[21:04](https://youtu.be/79sx6w13hC8?t=1264)已經實際代入［13531］這個例子說明那段程式碼可以反轉linked list，那[23:08](https://youtu.be/79sx6w13hC8?t=1388)［13579］的例子我想就不用再詳細代進程式碼走過這部份了，因為也只是反轉而已，重複性太高了，可以直接跳去講判斷不是回文回傳false那部分。
* [24:48](https://youtu.be/79sx6w13hC8?t=1487)複雜度沒有講原因。

### 第四次作業 他評02

+ intervewee
+ [7:00](https://youtu.be/79sx6w13hC8?t=1487)通常面試在分析時間複雜度的時候應該說明為何他的時間複雜度是O(N)，而不是直接說O(N)就帶過，應該要逐步說明每一行程式碼操作所需要的時間複雜度來做說明。
+ interviewer
+ [2:00](https://youtu.be/79sx6w13hC8?t=1487)題目設計的時候應該盡量避免直接講出 reverse linkedlist這種關鍵字，舉例：當我們需要用非連續記憶體空間記錄一串資料的時候，你會使用何種資料結構去儲存？進一步延伸到如果我們需要順序性來取得空間內部的資料，以及如果順序性需要反轉的話你會如何實作？這樣才可以避免背答案怪人。