[第二轮] 2/25-3/3 CareerCup 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 1's 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). That is, 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). That is, 617 + 295.
Output: 9 -> 1 -> 2. That is, 912.

发帖规范:
http://www.1point3acres.com/bbs/thread-48094-1-1.html
http://www.1point3acres.com/bbs/thread-32423-1-1.html

1 list.reverse()
2 loop to add
O(N)

https://gist.github.com/mettaworld/5036546
Java language
write a algorithm to add the two linked list as a summator. Then reverse the output linked list if ncessary.

Traverse two link list and add with the carry bit.
For the follow up, first reverse two operand link lists, then use former solution to get the sum, then reverse the result link list back.

https://gist.github.com/chrislukkk/5023048

逆序的好办，同步遍历两个链表，一位一位加。 run time O(N)
顺序的，如果是单向链表，没想出啥巧办法，只能把两个链表倒过来，然后同方法一，然后再倒回去。。。 run time O(N)
https://gist.github.com/Zuohr/5036972

liuzhe1218 发表于 2013-2-26 15:06
https://gist.github.com/mettaworld/5036546
Java language
write a algorithm to add the two linked l ...

1. 这个解法好像只能解三位数链表相加？
add test= new add(input1,input2);
这里面add类是哪里定义的？另外建议把算法写在类的方法里，或者是static method里，而不是constructor里。

2.  这里面函数调用的太多

public void reverse(){//  reverse the output linked list
                Link temp= new Link(0);
                int len= size()/2;
                for (int i=0;i<len;i++){
                        temp.setdata(get(i).getdata());
                        get(i).setdata(get(size()-i-1).getdata());
                        get(size()-i-1).setdata(temp.getdata());
                }                                
        }
如果想get(i)和get(size()-1-i)交换，用两个临时变量x, y保存下来再交换也好。更好的方法是把节点Link定义成private 内部类，这样可以让Link类对外不可见（不需要），同时data和next在LinkedList的方法里可以直接访问，不需要一堆getter,setter，用起来像C++的struct一样。
3. 这里好像有点问题，虽然编译运行应该都可以通过，但是我觉得本意应该不是用try block来保护throw new IndexOutOfBoundsException();吧（如果是请忽略我～）。
        public Link get(int i){
                if (i>size()-1||i<0){
                        try{
                                throw new IndexOutOfBoundsException();
                        }
                        catch (Exception e){
                                e.printStackTrace();
                        }
                }
                Link curr= first;
                for (int n=0;n<size();n++){
                        if(n==i)
                                return curr;
                        else
                                curr=curr.next;
                }
                return null;
        }

是不是应该是
if(i>size() -1 || i < 0)
  throw new IndexOutOfBoundsException();
然后所有用get(i)的地方用try block保护起来：
try {
  ...get(i)...
} catch (Exception e) {
...
}

zuohr 发表于 2013-2-26 18:13
1. 这个解法好像只能解三位数链表相加？
add test=[/backcolo ...

关于几位数，这个无所谓啊，输出的结果拿到位数就可以循环生成链表. 我这里只是写了个i<3, 这个可以动态.

zuohr 发表于 2013-2-26 18:13
1. 这个解法好像只能解三位数链表相加？
add test=[/backcolo ...

后面的确实第三个有点问题，改好了，第二个问题嘛，确实写get，set方法函数调用偏繁琐，但是要是保护内部数据的话，这样写也可以吧。

liuzhe1218 发表于 2013-2-26 23:25
后面的确实第三个有点问题，改好了，第二个问题嘛，确实写get，set方法函数调用偏繁琐，但是要是保护内部 ...

对的，所以我觉得可以把Link那个类放到LinkedList里做私有的内部类，这样对LinkedList的使用者完全不可见，而LinkedList的方法却可以自由访问，不需要调用函数。

* sol:
* 1. in this way, it acts as the same way we do the math, add two numbers, and pass forward the carry to next(larger significant digit)
* 2. keypoint here is to pass the carry down and return the this.node up, as we need the head
* follow up:
* 1. padding the linkedlist
* 2. wrapper for head, and int to tmp the carry
* 3. first node ready is the LSD, should be in the end of the listm, insertBefore)
*/
https://gist.github.com/longwei/5059080