【第三轮】6.23-6.29 CareerCup 2.5

【解题思路】
add by digit, keep the carry
FOLLOW UP:
considering the carry bit, it's impossible to proceed with prediction of carry bit, to avoid recursion, reverse the lists and perform reverse addition as implemented before, then reverse the summation and return
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/5832983c129d537298d5
【test case】
9999 + 1 = 10000

【解题思路】Reverse 2 linked list. Then add two linked lists as usual and reverse the result at end.
【时间复杂度】O(N)
【空间复杂度】O(N)
【gist link】https://gist.github.com/jason51122/1337cd3ec53243326f01

【解题思路】用同步遍历两个链表，各取出一个数，与进位做sum，保存carry。需要注意99+1.的情况。最高位还有1的情况。
一大早写状态差，写得乱七八糟。
Follow up: 待会儿写
【时间复杂度】O(m+n)
【空间复杂度】O(max(m,n))
【gist link】https://gist.github.com/guchang/d96d2d5bf2b8a6c67c7d

【解题思路】
  list->numer, add two number, sum->list
  list 初始化用的自己的 initialize 函数，要用到数组
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/xun-gong/6e06f9a82676012ab7aa

【解题思路】
reverse the two lists, and invoke addLists() to get
sumList, and reverse sumList to get correct result
【时间复杂度】O(max(M, N))
【空间复杂度】O(M + N + max(M, N)) (.....I'm not sure.......)
【gist link】https://gist.github.com/JoshuaTang/f71459369611d69d7354

//【解题思路】
//从头到尾遍历两条链，一位一位地相加，若有进位，则记录下，加到下一位。
//【时间复杂度】
//O(n+m)
//【空间复杂度】
//O(1)
//【gist link】
https://gist.github.com/Tsien/2b657a0bc23f0ca63350

【解题思路】
traverse two list at the same time and use the sum to create a new node

Follow Up: just reverse two list, use the previous method to add two list and reverse the result

【时间复杂度】
O(max(m, n))

【空间复杂度】
O(max(m, n))

【gist link】
https://gist.github.com/happyWinner/ed0fd5ca340f8f1cbcf8

follow up学习了下前面童鞋们的，用递归从后面开始加
时间复杂度 O(N)
空间复杂度： O(1)

https://gist.github.com/daisyang/5521dd686dcb792ff86d

想问一下这个题大家有没有考虑，　两个运算数的ｄｉｇｉｔｓ数目不一样的情况啊？感觉各种情况考虑完，写起来还挺复杂。
可能是因为我的Ｎｏｄｅ定义不太合理？

Idea: add two lists from the beginning, keep track of carrier

Time Complexity: O(m+n)
Space Complexity: O(max(m, n))

Solution2
Improvement: reduce the space complexity if we can change the original linkedList

if we first calculate the max length of the two input linkedList and using the max length LinkedList, as the result, we can reduce the space complexity to be O(1)

Time Complexity: O(m+n)
Space Complexity: O(max(m, n) – min(m, n))

Solution3
IDEA: Using Recursion

Improvement: same way, if we can modify the original LinkedList, we can implement it using Recursive within O(1) space complexity

Follow Up
Solution1
Idea: first reverse the two input linkedList, using addLinkedList() method and reverse the result list.

Solution2
Idea: Recursive algorithm, same with the idea in book

Notice
Consider the boundary
Consider the situation (9 -> 9 -> 9) + (2). Which the result will have four node rather than three
Make the code more cleanly is also very important.
create a virtual node and return the node.next can avoid to consider the null situation.
using ((list1 != null) ? list1.val : 0) rather than if-statement can more the code more clean.

Code:
http://www.jyuan92.com/post-465