package leetcode1_10;

/**（注意大整数）
 * You are given two linked lists representing two non-negative numbers.
 * The digits are stored in reverse order and each of their nodes contain a single digit.
 * Add the two numbers and return it as a linked list.

 Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
 Output: 7 -> 0 -> 8
 *
 * Created by DCLab on 11/2/2015.
 */
public class AddTwoNumbers {

    public static void main(String[] args) {
//        ListNode l11 = new ListNode(2);
//        ListNode l12 = new ListNode(4);
//        ListNode l13 = new ListNode(3);
//        l11.next = l12; l12.next = l13; l13.next = null;
//        ListNode l21 = new ListNode(5);
//        ListNode l22 = new ListNode(6);
//        ListNode l23 = new ListNode(4);
//        l21.next = l22; l22.next = l23; l23.next = null;
        ListNode l11 = new ListNode(0);
        l11.next = null;
        ListNode l21 = new ListNode(7);
        ListNode l22 = new ListNode(3);
        l21.next = l22; l22.next = null;
        ListNode node = new AddTwoNumbers().addTwoNumbers(l11, l21);
        while (node != null){
            System.out.print(node.val + " ");
            node = node.next;
        }
    }

    // Definition for singly-linked list.
    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        StringBuilder builder = new StringBuilder();
        while (l1 != null){
            builder.append(l1.val);
            l1 = l1.next;
        }
        String first = builder.toString();
        builder = new StringBuilder();
        while (l2 != null){
            builder.append(l2.val);
            l2 = l2.next;
        }
        String second = builder.toString();

        int diffLength = first.length() - second.length();
        if (diffLength >= 0) second = populateZero(second, diffLength);
        else first = populateZero(first, Math.abs(diffLength)); //TODO 注意取绝对值

        builder = new StringBuilder();
        int carryVal = 0;   //进位值
        for (int i = 0; i < first.length(); i++){
            int temp = first.charAt(i) - '0' + second.charAt(i) - '0' + carryVal;
            int remainder = temp % 10;
            carryVal = temp / 10;
            if (i == first.length() - 1){   //最高位
                builder.append(remainder).append(carryVal == 0 ? "" : "1");
            } else {
                builder.append(remainder);
            }
        }

        String ans = builder.toString();
        ListNode[] nodes = new ListNode[ans.length()];
        for (int i = 0; i < ans.length(); i++){
            nodes[i] = new ListNode(Integer.parseInt(String.valueOf(ans.charAt(i))));
        }
        for (int i = 0; i < ans.length(); i++){
            if (i == ans.length() - 1) nodes[i].next = null;
            else nodes[i].next = nodes[i + 1];
        }

        return nodes[0];
    }

    private String populateZero(String s, int populateLength){
        StringBuilder builder = new StringBuilder(s);
        for (int i = 0; i < populateLength; i++){
            builder.append('0');
        }
        return builder.toString();
    }

}

@@ -384,77 +384,69 @@
     
-public static void main(String%5B%5D args) %7B%0A//        ListNode l11 = new
+// Definition for singly-linked list.%0A    public static class
  Lis
@@ -454,23 +454,19 @@
 Node
-(2);%0A//
+ %7B%0A
         
 List
@@ -465,193 +465,118 @@
     
-ListNode l12 = new ListNode(4);%0A//        ListNode l13 = new ListNode(3);%0A//        l11.next = l12; l12.next = l13; l13.next = null;%0A//        ListNode l21 = new ListNode(5);%0A//        
+int val;%0A        ListNode next;%0A        ListNode(int x) %7B val = x; %7D%0A    %7D%0A%0A    public ListNode addTwoNumbers(
 List
@@ -577,32 +577,26 @@
 s(ListNode l
-22 = new
+1,
  ListNode(6)
@@ -596,15 +596,15 @@
 Node
-(6);%0A//
+ l2) %7B%0A
     
@@ -616,19 +616,21 @@
 istNode 
-l23
+dummy
  = new L
@@ -641,22 +641,20 @@
 ode(
-4
+0
 );%0A
-//
         
 l21.
@@ -653,121 +653,106 @@
     
-l21.next = l22; l22.next = l23; l23.next = null;%0A        ListNode l11 = new ListNode(0);%0A        l11.next = 
+ListNode p1 = l1, p2 = l2, p3 = dummy;%0A        int carry = 0;%0A        while(p1!=null %7C%7C p2!=
 null
-;
+)%7B
 %0A   
@@ -760,213 +760,124 @@
     
-ListNode l21 = new ListNode(7);%0A        ListNode l22 = new ListNode(3);%0A        l21.next = l22; l22.next = null;%0A        ListNode node = new AddTwoNumbers().addTwoNumbers(l11, l21);%0A        while (node 
+    if (p1!=null)%7B%0A                carry += p1.val;%0A                p1 = p1.next;%0A            %7D%0A            if (p2
 !=
- 
 null
@@ -895,42 +895,31 @@
     
-System.out.print(node.val + %22 %22);%0A
+    carry += p2.val;%0A  
     
@@ -930,19 +930,17 @@
     
-node = node
+  p2 = p2
 .nex
@@ -954,170 +954,201 @@
     
-%7D%0A
     %7D%0A
-%0A
     
-// Definition for singly-linked list.%0A    public static class ListNode %7B%0A        int val;%0A        ListNode next;%0A        ListNode(int x) %7B val = x; %7D
+        p3.next = new ListNode(carry%2510);%0A            p3 = p3.next;%0A            carry = carry/10;%0A        %7D%0A        if (carry==1) p3.next = new ListNode(1);%0A        return dummy.next;
 %0A   
@@ -1176,32 +1176,33 @@
 de addTwoNumbers
+1
 (ListNode l1, Li
@@ -2731,25 +2731,24 @@
 s%5B0%5D;%0A    %7D%0A
-%0A
     private 

Add Two Numbers