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

## <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. 解釋程式時的思路清楚