第二週的一開始,迎來了第一題 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 處理邁進了,每天都期待揪竟會出現什麼樣的題目呢。

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料