CareerCup 150

C.C 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.
 *
 * @author Jiateng
 */
public class CC2_5 {

    //Time O(max(m,n)), Space O(max(m,n))
    public static LinkedList sum1(LinkedList list1, LinkedList list2) {

        LinkedList list = new LinkedList();

        int len1 = list1.size();
        int len2 = list2.size();
        int len = Math.max(len1, len2);
        int carry = 0;
        int temp = 0;

        for (int i = 0; i < len; i++) {
            if (i >= len1) {
                if (carry == 1) {
                    list.addFirst((int) list2.get(i) + 1);
                } else {
                    list.addFirst(list2.get(i));
                }
                carry = 0;
            } else if (i >= len2) {
                if (carry == 1) {
                    list.addFirst((int) list1.get(i) + 1);
                } else {
                    list.addFirst(list1.get(i));
                }
                carry = 0;
            } else {
                temp = (int) list1.get(i) + (int) list2.get(i);
                //System.out.println(temp);
                if (carry == 1) {
                    list.addFirst(temp % 10 + 1);
                } else {
                    list.addFirst(temp % 10);
                }
                carry = temp / 10;
            }
        }

        if (carry == 1) {
            list.addFirst(1);
        }

        return list;
    }


    //Time O(max(m,n)), Space O(max(m,n))
    public static LinkedList sum2(LinkedList list1, LinkedList list2) {

        LinkedList list = new LinkedList();

        int len1 = list1.size();
        int len2 = list2.size();
        int len = Math.min(len1, len2);
        int dif = Math.abs(len1 - len2);
        int carry = 0;
        int temp = 0;
        int ten = 0;

        for (int i = 0; i < len; i++) {
            temp = (int) list1.get(len1 - 1 - i) + (int) list2.get(len2 - 1 - i);

            if (carry == 1) {
                ten = (temp + 1) % 10;
                list.addLast(ten);

            } else {
                ten = temp % 10;
                list.addLast(ten);
            }

            if (carry == 1) {
                carry = (temp + 1) / 10;
            } else {
                carry = temp / 10;
            }
        }

        if (len1 > len) {
            for (int i = 0; i < dif; i++) {
                temp = (int) list1.get(dif - i - 1);
                if (carry == 1) {
                    ten = (temp + 1) % 10;
                    list.addLast(ten);
                } else {
                    ten = temp % 10;
                    list.addLast(ten);
                }

                if (carry == 1) {
                    carry = (temp + 1) / 10;
                } else {
                    carry = temp / 10;
                }
            }

        } else {
            for (int i = 0; i < dif; i++) {
                temp = (int) list2.get(dif - i - 1);
                if (carry == 1) {
                    ten = (temp + 1) % 10;
                    list.addLast(ten);
                } else {
                    ten = temp % 10;
                    list.addLast(ten);
                }

                if (carry == 1) {
                    carry = (temp + 1) / 10;
                } else {
                    carry = temp / 10;
                }
            }
        }

        if (carry == 1) {
            list.addLast(1);
        }

        return list;
    }

    public static void main(String[] args) {

        LinkedList list1 = new LinkedList();
        LinkedList list2 = new LinkedList();

        list1.add(8);
        list1.add(5);
        list1.add(9);
        list2.add(9);
        list2.add(9);
        list2.add(7);
        list2.add(4);
        list2.add(5);

        LinkedList list = sum1(list1, list2);

        for (int i = list.size() - 1; i >= 0; i--) {
            System.out.print(list.get(i));
            if (i != 0) {
                System.out.print(" -> ");
            }
        }
        System.out.println();

        list = sum2(list1, list2);

        for (int i = list.size() - 1; i >= 0; i--) {
            System.out.print(list.get(i));
            if (i != 0) {
                System.out.print(" -> ");
            }
        }
        System.out.println();
    }
}