Problem#
給你兩個 linked-list 問你相加回傳多少
Follow-up: 在不 reverse input 的情況下解這題
測資限制#
- $1 \le n \le 100$: number of nodes
- $0 \le val \le 9$
想法#
直覺做法就是從低位數加到高位數，像是直式加法那樣，但 input 是由高位排到低位，且 follow-up 邀求不能反轉 list
不反轉也可以直接加，但是就麻煩了點
- 計算兩個 list 的大小
- 將大小較小的 list 用
0填充前面到與較大的 list 相同長度 - 加法 & 進位
- 時間複雜度: $\mathcal{O}(n)$
- 空間複雜度: $\mathcal{O}(1)$
AC Code#
心得#
說不能反轉 list ，但官方題解竟然有用 stack 的，來鬧的 484 XD
我以為這種 linked-list 的題目都是要在 list 上完成的ㄏㄏ