【第三轮】6.23-6.29 CareerCup 2.5

============================================================================
Solution        : add cooresponding value of two linkedlist and mark down the carry in
                   FolloUp:
                   using recusion to add two numbers and return carry
                   and save result in a list
                   reverse list and save to a linkedlist
Time Complexity : O(n)
Space Complexity: O(m, n)
Gist Link       : https://gist.github.com/habina/a03e10e925ef43d95e71
============================================================================

【解题思路】Add list from the head one by one, generate a new list to store the result
【时间复杂度】O(M+N)
【空间复杂度】O(max(M,N))
【gist link】https://gist.github.com/bitcpf/b4233e9747980b42fdb5

【解题思路】没思路...先发前半部分的,   FollowUP写了半天老出问题一怒之下删掉了....  之后补上吧, 头痛,睡觉去了
【时间复杂度】O(M+N)
【空间复杂度】O(MAX(M, N))
【gist link】https://gist.github.com/weazord/65bb39b3ae739b7a5b10

【解题思路】写的有点复杂，很多判断条件。分别判断l1,l2,carrier 空的情况。  folow up还没写，应该是carrier加在node前面有点麻烦把
【时间复杂度】O(M+N)
【空间复杂度】O(MAX(M, N))
【gist link】
https://gist.github.com/yokiy/62724b32df4c2dc58121

这题解法太多，完全写吐了啊，就写两个自己想的方法吧

【解题思路】Iterative,从头扫到尾，carry一个进位的int一起相加
【时间复杂度】O(max(M,N))
【空间复杂度】O(max(M,N))

FOLLOW UP：
【解题思路】把list反转过来然后和上面一样，最后再把结果反过来。
【时间复杂度】 O(m+n)
【空间复杂度】O(max(m,n)) if we are allowed to mutate the original
         * lists when reverting them (otherwise space is O(m+n) not implemented

【gist link】
https://gist.github.com/XiaoxiaoLi/88bd156d235d6a6e7d08

【解题思路】just normal sum algorithm. FOLLOW UP: reverse, sum and recover
【时间复杂度】O(max(N,M))
【空间复杂度】O(1), constant extra space
【gist link】https://gist.github.com/nealhu/19b6891766bd9ab4b83a

【解题思路】first read number in the list in reverse order and sum up two numbers, then store the result in a list in reverse order   
Follow up: read number in the list in order and sum them up, then store the result into a list using previous method, then reverse this list
【时间复杂度】O(m+n)
【空间复杂度】O(max(m,n))
【gist link】https://gist.github.com/startupjing/29e961b17dcf6b11018e

【解题思路】
在生成第一个linkedlist时在头上插入新元素，之后把输出结果分为两个数后相加，再把答案转化为String，利用charAt分别读取每一位后插入新list后倒序输出
没有写follow up，二者惟一的区别就是create一个是输入0，另一个输入目标List的长度
【时间复杂度】
O(m+n)
【空间复杂度】
O(max(m,n))
【gist link】直接代码
import java.util.*;

class Node{
        private Node next;
        private Object data;
       
        public Node(){
                this(null,null);
        }
        public Node(Object data){
                this(data,null);
        }
        public Node(Object data, Node next){
                this.data = data;
                this.next = next;
        }
        public Object getData(){
                return data;
        }
        public void setData(Object data){
                this.data = data;
        }
        public Node getNext(){
                return next;
        }
        public void setNext(Node next){
                this.next = next;
        }
}

class LinkedList{
        Node head = new Node();
        Scanner sc = new Scanner(System.in);
        public void create(int k){
                for(int x=sc.nextInt();x!=0;x = sc.nextInt())
                        insert(0,x);
        }
        public void insert(int i, Object x){
                Node p = head;
                int j = -1;
                while(p.getNext()!=null && j<i-1){
                        p = p.getNext();
                        j++;       
                }
                Node s = new Node(x);
                s.setNext(p.getNext());
                p.setNext(s);
        }

        public void display(){
                Node p = head.getNext();
                while(p!=null){
                        System.out.print(p.getData()+" ");
                        p = p.getNext();
                }
        }

        public int getLength(){
                Node p = head.getNext();
                int s = 0;
                while(p!=null){
                        s++;
                        p = p.getNext();
                }
                return s;
        }

        public int add(int b){
                Node p = head.getNext();
                int j = 0;
                int sum1 = 0;
                int t = 0;
                int c = b-1;
                int sum2 = 0;
                while(j<b){
                        t = (int)Math.pow(10,c);
                        sum1 +=(int)p.getData()*t;
                        p = p.getNext();
                        c--;
                        j++;
                }
                t = 0;
                c = b-1;
                while(p!=null){
                        t = (int)Math.pow(10,c);
                        sum2 +=(int)p.getData()*t;
                        p = p.getNext();
                        c--;
                        j++;
                }
                return sum1+sum2;
        }
}

public class Q2_5{
        public static void main(String[] agrs){
                LinkedList L = new LinkedList();
                LinkedList M = new LinkedList();
                Scanner sc = new Scanner(System.in);
                System.out.print("please input elements, 0 as an End:");
                L.create(0);
                L.display();
                System.out.println();
                int a = L.getLength();
                String r = String.valueOf(L.add(a/2));
                int j = r.length()-1;
                int s = 0;
                while(s<=j){
                        M.insert(0,r.charAt(s));
                        s++;
                }
                M.display();
                               
        }
}
【Test case】
in:8->7->6->5->4->3->2->1
out:6->8->0->3->1
follow up懒得写了，就是再新生成两个linkedlist（如K和N），K.create(L.length)就可以了

【解题思路】
Give each digit the right weight, then we get two numbers. (singlelinked is ok)
1. In case A, just iterate two list once
2. In case B, need to iterate them twice since need to get their length
【时间复杂度】O(m+n)
【空间复杂度】O(1)
【gist link】https://github.com/FinalF/CarrerUp/blob/master/addOperation.java

【解题思路】
zero padding the shorter list, then add by digit together with carry bit. DON'T forget the last carry bit!
FOLLOW UP:
It's impossible to proceed with prediction of carry bit, thus 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