#38 Coding 面試 - LeetCode #2 Add Two Numbers

原文題目 https://leetcode.com/problems/add-two-numbers/

這題是個基本的 Linked List 考題,如果題到這類型的 List 題目,若題目沒特別說的話,就一律想成是 Single Linked List 了.其實,我個人不是很喜歡 List 考題,原因是大部份的問題都蠻無聊的,可能就在 List 上把元素搬來搬去,而且不一定會有一個很好的邏輯來搬這些元素,所以就會造成一個 function 寫的長長的.像這一題就是這樣.

題目給了兩個 input list,要把每個元素加在一起後,然後輸出一個最後的 list.其實也蠻簡單的,你只要在這兩個 input list 上一個一個元素去拜訪,然後把加起來的答案寫到新的位置上,同時再注意進位的事情.並且你也要考慮到兩個 input list 的長度可能是一樣長,也可能是不一樣長,甚至可能是空的.如果你按照這個想法寫,答案就可以寫的出來.

但是,就這麼簡單嗎 ? 基本上是的,但要注意一件事,上面的想法是會製造出另一個新的 list,算到最後把這個 list return 出去.這樣做的話就等於空間複雜度是 O(n+m) 了,假設 n,m 分別是兩個 input list 的長度.

所以,比較好的做法是讓空間複雜度變成 O(1),也就是說每當計算一次元素的加法時,就把答案寫到某一個 input list 上,最後 return 這一個 input list 就行了,所以就不需要宣告出其他不是 O(1) 的空間.

參考的程式碼如下:



沒錯吧,又臭又長! 如果你能想到更好的方法來簡化以上的程式碼,再麻煩你教教我! ^_^

Share:

0 意見:

張貼留言