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

这道题有多种解法：

  (1) 将两个链表转化成数字，然后数字运算。然后再转成链表：

我认为这也是一种思路。尽管运算麻烦点，可是思路简单。

但注意：整数运算非常easy超出范围，导致返回错误结果。所以我们拿double或者float来接受数字就好了。可是在推断的时候，必须用while(num>=1)来推断是否已经将num的数取完。由于整数会自己主动取整。float和double要手动处理下。

在时间复杂度上。要比（2）耗时一点，只是也是 O(n)时间.

（2）从两个链表头遍历到尾，用一个carry常量来代表进位。既然是逆序排列，我们就直接遍历就好了。

可是有一点要注意，就是题目并没有说两个链表是一样的长度，那我们如同mergesort那样，把多余的那一截，加上进位进行运算。

最后还得推断下：假设carry还是等于1，那说明新的数字要比之前的数多一位。 比方99999+1这种。所以这种情况。再加上一个1节点就可以。

代码反复的地方有点多，应该能够把后面两个while优化一下，整合到一起。可是思路是没有问题的。

O（n）时间 leetcode一次通过。

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {		if (l1 == null && l2 == null)			return null;		double num1 = ListToNumber(l1);		double num2 = ListToNumber(l2);		return NumberToList(num1 + num2);	}	public static ListNode NumberToList(double num) {		ListNode head = new ListNode(0);		ListNode res = head;		if (num < 10)			return new ListNode((int) num);		while (num >= 1) {			int lastdigit = (int) (num % 10);			num = num / 10;			head.next = new ListNode(lastdigit);			head = head.next;		}		return res.next;	}	public static double ListToNumber(ListNode head) {		if (head == null)			return 0;		double num = 0;		double base = 1;		while (head != null) {			num += head.val * base;			head = head.next;			base = base * 10;		}		return num;	}

Solution 2（推荐）

public  ListNode addTwoNumbers(ListNode l1, ListNode l2) {	        if(l1==null && l2==null) return null;	        ListNode res=new ListNode(1);	        ListNode dummy=res;	        int carry=0;	        while(l1!=null && l2!=null){	            int val=l1.val+l2.val+carry;	            if(val>9){	                val=val%10;	                carry=1;	            } else {	                carry=0;	            }	            res.next=new ListNode(val);	            res=res.next;	            l1=l1.next;	            l2=l2.next;	        }	        	        while(l1!=null){	            int val=l1.val+carry;	            if(val>9){	                val=val%10;	                carry=1;	            } else {	                carry=0;	            }	            res.next=new ListNode(val);	            res=res.next;	            l1=l1.next;	        }	        	        while(l2!=null){	            int val=l2.val+carry;	            if(val>9){	                val=val%10;	                carry=1;	            } else {	                carry=0;	            }	            res.next=new ListNode(val);	            res=res.next;	            l2=l2.next;	        }	        	        if(carry==1){	            res.next=new ListNode(1);	        }	        	        return dummy.next;	        	    }