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 contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)Output: 7 -> 0 -> 8
Subscribe to see which companies asked this question.
倉鼠翻譯一下題目：給你兩個非空鏈表，每個鏈表代表一個數(shù)，把這兩個數(shù)加起來，返回結(jié)果。結(jié)果也是以鏈表的形式返回。
稍微特殊一點的地方是，給的鏈表是按數(shù)字的每一位倒著給的，比如 123 一百二十三 給的鏈表是 3 -> 2 -> 1
這樣如果輸入 (2 -> 4 -> 3) 和 (5 -> 6 -> 4) 兩個鏈表，代表 342 和 465，加出來的結(jié)果應(yīng)該是 807，返回的結(jié)果應(yīng)該是 7 -> 0 -> 8
這就是一個簡單的鏈表節(jié)點的定義。包含兩部分：
next 是一個鉤子，鉤住鏈表里的下一個節(jié)點，所以我們能從每個節(jié)點順到下一個節(jié)點。value 是節(jié)點要存的值，什么都可以，我們現(xiàn)在用一個 int 作為例子。
節(jié)點當(dāng)然不帶頭結(jié)點，鏈表才帶頭結(jié)點呀。
所以大家知道鏈表是什么了嘛？鏈表就是一系列這樣的節(jié)點，第一個連著第二個，第二個連這第三個…… 這樣。第一個節(jié)點稱為頭結(jié)點，最后一個節(jié)點稱為尾節(jié)點
繼續(xù)講鏈表哈。我們跟數(shù)組來對比一下。數(shù)組是內(nèi)存里一段連續(xù)的空間，第一個元素挨著第二個元素，第二個元素挨著第三個元素…… 而鏈表在內(nèi)存里可能是不連續(xù)的，第一個節(jié)點和第二個節(jié)點內(nèi)存上并不連續(xù)，但是第一個節(jié)點有個 next 指針指向第二個節(jié)點，第二個節(jié)點有個 next 指針指向第三個節(jié)點……
不要被“指針”這倆字嚇到，我發(fā)現(xiàn)很多人都怕這個詞，但實際咱們平常寫 OC 的，@property (nonatomic, strong) LinkListNode* next; 這就是一個指針。就按著一個 property 去理解就好。
好好，接著講：剛才代碼示例了節(jié)點的結(jié)構(gòu)，下面來示例一下鏈表的結(jié)構(gòu)。就是記住了倆節(jié)點，頭結(jié)點和尾節(jié)點。
有時候連尾節(jié)點都不給，比如本題，只給了頭結(jié)點。但你通過 next 一路順下去，也能找到尾節(jié)點了。
簡單講一下鏈表怎么操作。插入一個節(jié)點，分為三種情況：最基本的情況，比如之前是 a -> b，要插在 a、b之間，就改成這樣 a->c->b 即可，讓 a.next = c, c.next = b；另外兩種特殊情況，插在頭結(jié)點之前，只需讓 c->a，然后把鏈表的 head 從 a 改成 c；插在尾節(jié)點之后，只需讓 b->c ，然后把鏈表的 tail 從 b 改到 c。
刪除一個節(jié)點，大家可以類推一下……
訪問某個位置的節(jié)點，比如找第 5 個節(jié)點，只能從頭結(jié)點找齊，頭結(jié)點的 next 找第二個節(jié)點，第二個的 next 找第三個節(jié)點…… 一直找到第5個
我們已經(jīng)有了數(shù)組，為啥還要用鏈表呢？我們來對比一下數(shù)組和鏈表的優(yōu)勢和劣勢。數(shù)組的優(yōu)勢是，它的空間是連續(xù)的。所以我可以“隨機(jī)訪問”，比如 我現(xiàn)在就要知道第10個元素，我可以 array[10]，而鏈表就完全不行，像剛才說的，得從頭結(jié)點開始往下順。數(shù)組訪問某個位置的元素，時間復(fù)雜度是 O(1) 而鏈表是 O(n)
但數(shù)組也有劣勢，就在于插入和刪除。比如我要刪除數(shù)組第3個元素，那么第2個元素和第4個元素之間就會出現(xiàn)一個空檔。數(shù)組的空間是連續(xù)的，為了不讓它出現(xiàn)空檔，我們必須把第4個元素挪到第3個元素的位置，第5個元素挪到第4個元素的位置…… 一個一個往前挪。而鏈表就很輕松，直接把第二個節(jié)點的 next 指向第四個節(jié)點，第三個節(jié)點就從鏈表里掉下來啦。
數(shù)組在中間位置插入和刪除，時間復(fù)雜度是 O(n) 而鏈表是 O(1)
最后一個next指向NULL
