[Leetcode]2:Add Two Numbers

Link : https://leetcode.com/problems/add-two-numbers/

Problem :
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

把兩個linklist裡面的node值相加的題目,加法的進位方式跟一般我們常用的不太一樣。舉例來說(參考下面的圖)

Example 1 :
2 -> 4 ->3
5-> 6 -> 4
7 ->10 ->7 (進位以後 : 7 ->0(留個位數就好,十位數1進位到右邊) -> 8(7+1))

Example 3 :
9 -> 9 -> 9 -> 9 -> 9 -> 9 -> 9
9 -> 9 -> 9 -> 9
18 -> 18 -> 18 ->18 -> 9 -> 9 -> 9
進位步驟:
8 ->19 -> 18 -> 18 -> 9 -> 9 -> 9
8 -> 9 -> 19 -> 18 -> 9 -> 9 -> 9
8 -> 9 -> 9 -> 19 -> 9 -> 9 -> 9
8 -> 9 -> 9 -> 9 -> 10 -> 9 -> 9
8 -> 9 -> 9 -> 9 -> 0 -> 10 -> 9
8 -> 9 -> 9 -> 9 -> 0 -> 0 -> 10
8 -> 9 -> 9 -> 9 -> 0 -> 0 -> 0 -> 1

圖來自leetcode

Thoughts :
1. new一個新的 linklist來存加完的result。
2. 把 l1 的第一個 node 跟 l2 的 第一個 node 加起來。
3. 檢查個位數跟十位數,個位數存起來,十位數往後一位存。

Solution :

time complexity = O(n)?, space complexity = O(1)?

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store