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