###### tags: `資訊產業導論`
# info2021-homework1
> 貢獻者: 李馬克 Mark

## 測驗一、 206. Reverse Linked List
已知不存在環狀結構，且為單向鍊結串列，因此只須將 linked list 其內節點指向反轉即可

對應程式碼如下

//定義 Node 結構
class Node() {
    int value;
    Node nextNode;
    Node(int val) { this.value = value; }
}


class Solution() {
    // 疊代版本
    private Node reverseNodes(Node head){
        Node curr = head;
        Node prev = null;
        
        while(curr != null) {
            Node temp = curr.nextNode;
            curr.nextNode = prev;
            prev = curr;
            curr = temp;
        }
        
        return prev;
    }

    // 遞迴版本
    private Node reverseNodeRecursive(Node head) {
        if(head == null || head.nextNode == null) {
            return head
        }
        
        Node newNode = reverseNodeRecursive(head.nextNode)
        head.nextNode.nextNode = head;
        head.nextNode = null;
        
        return newNode;
    }
    
    private printLinkedList(Node head) {
        while(head != null) {
            System.out.print(head.value + " ");
            head = head.nextNode;
        }
        System.out.print("\n");
    }
    
    public static void main(String[] args) {
        Node head = new Node(1);
        head.nextNode = new Node(2);
        head.nextNode.nextNode = new Node(3);
        head.nextNode.nextNode.nextNode = new Node(4);
        head.nextNode.nextNode.nextNode.nextNode = new Node(5);
        
        printLinkedList(reverseNodes(head));
        printLinkedList(reverseNodeRecursive(head));
    }
}

輸出：

5 4 3 2 1
5 4 3 2 1

## 測驗二、 141. Linked List Cycle
Given head, the head of a linked list, determine if the linked list has a cycle in it.
對應程式碼如下

//定義 Node 結構
class Node() {
    int value;
    Node nextNode;
}

class Solution() {

    // 用 HashSet 檢查是否有重複的 Node
    private boolean hasCycle(Node head) {
        HashSet<Node> set = new HashSet();
        
        while(head != null) {
            if(set.contains(head)){
                return true;
            } else {
                set.add(head);
                head = head.nextNode;
            }
        }
        return false;
    }
    
    // 利用兩個 Node 的前進速度不同，檢查是否會相撞
    private boolean hasCycleWithTwoNodes(Node head) {
        if (head == null) {
            return false;
        }
        
        Node slow = head;
        Node fast = head.nextNode;
        
        while(slow != fast) {
            if (fast == null || fast.nextNode == null) {
                return false;
            }
            slow = slow.nextNode;
            fast = fast.nextNode.nextNode;
        }
        
        return true;
    }
    
    public static void main(String[] args) {
        Node head = new Node(3);
        head.nextNode = new Node(2);
        head.nextNode.nextNode = new Node(0);
        head.nextNode.nextNode.nextNode = new Node(-4);
        head.nextNode.nextNode.nextNode.nextNode = head.nextNode;
        
        System.out.println(hasCycle(head));
        System.out.println(hasCycleWithTwoNodes(head));
    }
}

輸出：

true
true

:::info
討論項目
- 是否能在 O(1) Memory Space 下解決此問題
:::

## 測驗三、 142. Linked List Cycle II
Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

class Node() {
    int value;
    Node nextNode;
}

class Solution() {
    // 用 HashSet 找出產生 cycle 的 Node
    private Node beginCycleNode(Node head) {
        HashSet<Node> set = new HashSet();
        
        while(head != null) {
            if(set.contains(head)) {
                return head;
            } else {
                set.add(head);
                head = head.nextNode;
            }
        }
        
        return null;
    }
    
    // 找出"開始"、"產生 cycke"、"碰撞"此三個 Node 的距離關係
    private Node beginCycleNodeTwo(Node head) {
        Node fast = head;
        Node slow = head;
        
        while(slow != null && fast != null) {
            slow = slow.nextNode;
            fast = fast.nextNode.nextNode;
            
            if(slow == fast) {
                break;
            }
        }
        
        if (fast == null || fast.nextNode == null) {
            return null;
        }
        
        Node explpore = head;
        while(explore == slow) {
            explore = explore.nextNode;
            slow = slow.nextNode;
        }
        return explore;
    }
    
    public static void main(String[] args) {
        Node head = new Node(3);
        head.nextNode = new Node(2);
        head.nextNode.nextNode = new Node(0);
        head.nextNode.nextNode.nextNode = new Node(-4);
        head.nextNode.nextNode.nextNode.nextNode = head.nextNode;
        
        System.out.println(beginCycleNode(head).value);
        System.out.println(beginCycleNodeTwo(head).value);
    }

}

輸出：

2
2

:::info
討論項目
- 是否能在 O(1) Memory Space 下解決此問題
:::
## 檢討與改進
### Interviewer
1. 提出的問題都太淺，缺乏從 Interviewer 角度延伸問題與更深入的討論（換位思考的能力）
2. 可以問題目裡面的演算法是否有在實務中使用過
### Interviewee
1. 解析問題花費太多時間，應該掌握在 15~30 秒左右說完方法（掌握時間的能力）
2. 若音調能夠再多點變化，更能夠讓 Interviewer 專心聽完
3. 本次使用 hackmd 而非 Google docs coding，下次可採用 google docs 會更有真實感
4. 搭配白板分析問題，能夠更清楚的表達想法
5. 有盡可能在過程中做到 REACTO，但還是會忘記要做 Optimization