30-Day LeetCoding Challenge (Day8)

第二週的一開始，迎來了第一題 Linked-list 876. Middle of the Linked List，給定一個單向 Linked-list，找出他的中間節點。

乍聽之下好像蠻簡單的，實際寫起來也真的不難XD
最直覺的寫法就是先跑一次看總共有幾個，然後再把 ptr 指到中間的就可以了。

從這篇開始節省篇幅只寫 function 的實作，一些加速（sync_with_stdio/cin_cout.tie()…etc）的就先不寫在 code 裡，有興趣可以再參考 Day1 的介紹～

    ListNode* middleNode(ListNode* head) {
        ListNode* ans = head;
        int cnt = 1;
        while(ans->next != NULL) {
            cnt++;
            ans = ans->next;
        }
        
        ans = head;
        
        for(int i=0; i<cnt/2; i++)
            ans = ans->next;
        
        return ans;
    }

另外一個想法是用兩個 ptr，一個走一步，一個走兩步，只是在處理邊界問題時要小心就是了。

    ListNode* middleNode(ListNode* head) {
        ListNode* one = head;
        ListNode* two = head;

        while(true) {
            if(two->next != NULL && two->next->next != NULL) {
                one = one->next;
                two = two->next->next;
            } else if(two->next != NULL && two->next->next == NULL) {
                one = one->next;
                break;
            } else break;
        }
        return one;
    }

看了官方解答發現耍笨了，不需要在 while 裡面處理一堆判斷，只要看現在跟下一個是不是 NULL 就好了。

    ListNode* middleNode(ListNode* head) {
        ListNode* one = head;
        ListNode* two = head;

        while(two != NULL && two->next != NULL ) {
            one = one->next;
            two = two->next->next;
        }

        return one;
    }

更神奇的是結合前一週學到的 vector，把每個 node 都 push 進去，活用 vector 直接 return 中間的 index。
雖然說這樣 Space Complexity 變 O(N)，但不得不說真的是打開一扇新大門，實在是太神奇了傑克。

    ListNode* middleNode(ListNode* head) {
        vector<ListNode*> v = {head};

        while(v.back()->next != NULL ) {
            v.push_back(v.back()->next);
        }

        return v[v.size()/2];
    }

好像開始要朝一些更進階一點的 DS/Algo 處理邁進了，每天都期待揪竟會出現什麼樣的題目呢。