【第三轮】6.23-6.29 CareerCup 2.5

2.5
You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the Ts digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.
EXAMPLE
Input:(7-> 1 -> 6) + (5 -> 9 -> 2).Thatis,617 + 295.
Output: 2 -> 1 -> 9.That is, 912.
FOLLOW UP
Suppose the digits are stored in forward order. Repeat the above problem. EXAMPLE
Input:(6 -> 1 -> 7) + (2 -> 9 -> 5).Thatis,617 + 295.
Output: 9 -> 1 -> 2.That is, 912.

回复解法可以按照以下格式来

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------Optional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

Notice：
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子，除了贴解法，欢迎讨论，集思广益
4、任何未尽之处，欢迎回报名帖提问，我会进一步作出修改。

【解题思路】
在生成第一个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)就可以了

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

【解题思路】用两个iterator，从链表的第一位，每两个数和前一个的进位相加，结果取个位add 进结果的链表，更新进位。
【时间复杂度】O(m+n)
【空间复杂度】O(max(m,n))
【gist link】https://gist.github.com/chouclee/97d1aa3bf0461fa82642

【解题思路】妈的, 花了我1个多小时, 终于写了个很短的...
【时间复杂度】O(m+n)
【空间复杂度】O(max(m,n))
【gist link】https://gist.github.com/gaoyike/e150277cbd245298488a

【解题思路】
比较暴力的写了很多判断条件，主要就是考虑进位和list的排序，使用了addlast方法，虽然不是很好，但是个人觉得比较易懂。
【时间复杂度】
O(max(m,n))
【空间复杂度】
O(max(m,n))
【gist link】
https://gist.github.com/UncleGarden/15892158c55be826ecb0

【解题思路】
add two lists from the beginning, keep track of carrier.
FOLLOWUP: count the length of the two lists first, add 0s for shorter list at the beginning, recursively call addLast()
【时间复杂度】
O(M+N)
【空间复杂度】
O(max(M,N))
【gist link】
https://gist.github.com/iwilbert/d0ef097a92c9ce096e95

【解题思路】
- Go through list, add digit by digit
- Keep tracking the overflow value

Follow up
- reverse the input list, use original add function, add reverse answer back

【时间复杂度】
O(M +  N)

【空间复杂度】
O(max(M,N))

【gist link】
https://gist.github.com/chrislukkk/50f3322f76256c71552a

【解题思路】
新建 list，若 a, b 或进位任一不为0，则产生新节点添在后面。
follow up : 先将两个 list 补充成一样长，然后利用递归计算
【时间复杂度】
O(m+n)
【空间复杂度】
O(Max(m,n))
【gist link】https://gist.github.com/JoyceeLee/6ff64e9e5b7dab0c85b2

【解题思路】
l1,l2为空，则为空；不为空，相加，按法则计算
【时间复杂度】
O(m+n)
【空间复杂度】
O(Max(m,n))
【gist link】https://gist.github.com/hilda8519/f5d60e652c48785b924a

【解题思路】  for the follow up question, we need to firstly compare the length of two linkedlist and pad zeroes at the front of the longer one.   Then use recursive method to calculate the sum
【时间复杂度】
O(Max(m,n))
【空间复杂度】
O(Max(m,n))
【gist link】  [url=https://gist.github.com/jyhjuzi/2c61556d5cbe6857a23d][/url]