[LeetCode][C++] 用乾淨的方式寫 #19 Remove Nth Node From End of List
又是一個資料結構練習? 但仔細一看他希望我們做 one pass 就可以輸出答案。
我 OK，你先走 n 步
如果我們用左右兩個指標，讓右邊的指標先走 n 步，會發生什麼事?
我們就先模擬看看，當右邊的人一踩到 nullptr，左邊的指標在哪?
假設 n=2 我們看到左邊的指標正好指著要刪除的 node，好像就做完了。
問題是，現在要怎麼刪除左邊的人? 單向的 linked list 一旦往後走就不能回頭了，我們想把 2 接到 4 現在就卡死動彈不得了。
我 OK，你先走 n + 1 步
既然我們想要把左右兩邊的指標再距離寬一點，那我們就會很直覺的想把 n + 1 再模擬看看:
但如果 n 剛好等於 linked list 長度，右邊先跑 n + 1 步的話左邊的人不就會超出範圍?
所以我們就用一個常見的技巧，創一個虛擬的 node，LeetCode 上叫做 dummy，不過我覺得叫 root 比較好，比較有起始點的感覺。
當右邊指標撞到 nullptr 左邊指標的下一個人剛好就是要刪除的對象，這時候就不會有問題。
Boundary Cases
養成好習慣我們還是要稍微想一下比較容易出問題的邊界條件:
- 如果 n=1 會不會有問題? 不會
- 如果 n=size 會不會有問題? left 會在 root 的位置，刪除下一個人也不會有問題
好讀的 C++ 程式碼
我們想要讓維護的人一看就知道程式碼在做什麼，所以我的習慣就是用小小的 function 加上很好懂得名稱告訴別人我 function 在做什麼，而且一次只做一件事。
這樣 removeNthFromEnd 就會看起來很清爽:
class Solution {
public:
ListNode *removeNthFromEnd(ListNode *head, int n) {
ListNode root(0, head);
ListNode *left = &root;
ListNode *right = &root;
right = moveNSteps(right, n + 1);
while (right != nullptr) {
left = moveNSteps(left, 1);
right = moveNSteps(right, 1);
}
deleteNextNode(left);
head = root.next;
return head;
}
ListNode *moveNSteps(ListNode *node, int numSteps) {
for (int i = 0; i < numSteps; i++) {
assert(node != nullptr);
node = node->next;
}
return node;
}
void deleteNextNode(ListNode *node) {
ListNode *nextNode = node->next;
assert(nextNode != nullptr);
node->next = nextNode->next;
delete nextNode;
}
};
還有一些小細節是防止錯誤用的:
- 第 4 行為什麼不用 new ListNode 的方式?
- 不然就會像 LeetCode 上的解答最後忘了把 dummy 刪除，造成 memory leak
- 這邊這樣寫一離開 function，root 自然就會被刪除
- 第 13 行為什麼要先讓 head = root.next?
- 因為我們刪除 left 有可能會刪到 head，怕以後修改的人會不小心用到已經被刪除的 head，所以我們趕緊先把他修正
- 如果沒修正我們會把 13 行之後的 head 叫做 dangling pointer
- 第 19 和 27 行為什麼要用 assert?
- 有時候加一些 assert 可以幫助 debug，也避免一些 nullptr 存取造成奇怪的問題
- 兩處都是為了要避免應該不可能發生的條件，不然 nullptr->next 不知道會發生什麼事 (undefined behavior)，常常令人頭痛
Submission
這題主要是資料結構與演算法的設計，和速度/記憶體應該就沒什麼關係了:
結語
我其實一開始是用 nullptr 來當作開頭的，不過程式碼不僅會比較長，一個致命缺陷就是會分不清楚到底 nullptr 是代表開頭還是結尾，所以後來還是改成用一個 root 的方式。
不過說實在的，LeetCode 說 linked list 最長也才 30，恐怕 one pass 和 two pass 真的看不出什麼差別。討論區有人在爭論說 one pass 和 two pass 時間根本一樣，不過實際上跑起來 one pass 可能還是會快一點，詳細的說明請看 x86hacker 在討論區的回答。
留言
發佈留言