You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Follow up:

What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)Output: 7 -> 8 -> 0 -> 7 大数加法+链表操作，用长整型会溢出的。

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */class Solution {    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {        String s1 = toStr(l1);        String s2 = toStr(l2);        return toNode(addTowStr(s1, s2));    }        private String toStr(ListNode node) {        StringBuilder sr = new StringBuilder();        if (node == null)            return sr.toString();        while (node != null) {            sr.append(node.val);            node = node.next;        }        return sr.toString();    }        private ListNode toNode(String str) {        if (str == null)            return null;                ListNode cur = new ListNode(str.charAt(str.length()-1)-'0');        ListNode head = cur;        for (int i=str.length()-2; i>=0; i--) {            cur.next = new ListNode(str.charAt(i)-'0');            cur = cur.next;        }        return head;    }        private String addTowStr(String s1, String s2) {        if (s1 == null || s1.length() <= 0)            return s2;        if (s2 == null || s2.length() <= 0)            return s1;                if (s1.length() < s2.length()) {            String t = s1;            s1 = s2;            s2 = t;        }        int minLen = s2.length();        int maxLen = s1.length();        int over = 0;        StringBuilder ret = new StringBuilder();        for (int i=minLen-1,j=maxLen-1; i>=0 && j>=maxLen-minLen; i--,j--) {            int sum = (s1.charAt(j)-'0') + (s2.charAt(i)-'0') + over;            if (sum < 10) {                ret.append(sum+"");                over = 0;            }            else {                ret.append((sum % 10)+"");                over = sum / 10;            }        }                for (int i=maxLen-minLen-1; i>=0; i--) {            int sum = (s1.charAt(i)-'0') + over;            if (sum < 10) {                ret.append(sum+"");                over = 0;            }            else {                over = sum / 10;                ret.append((sum % 10)+"");            }        }        if (over > 0)            ret.append(over);        return ret.toString();    }        }