问题

You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in forward 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.

Have you met this question in a real interview? Yes
Example
Given 6->1->7 + 2->9->5. That is, 617 + 295.

Return 9->1->2. That is, 912.

分析

注意链表是顺序来表示数字的。如果使用其它的数据结构来存储再做加法，肯定是可以的，但使用到了空间，在这里就不演示了。
如果不使用多余的空间还有两种思路:
一是先把每个链表都反转， 得到结果之后再反转回来。
二是本文要介绍的方法，就是从高位往低位来做加法。
需要记录不为9的那个位置，因为如果是9的话，后边可能产生的进位，会让它本身再进位。所以我们用一个pre来记录最后一个不为9的位置。每当后边产生一个进位的时候，pre本身肯定是要加1的。然后从pre到当前节点之间的(不包含两个边界)的所有节点都要变成0(也可能没有)。当前的节点因为产生了进位，所以肯定不会为9，把pre指向当前的节点，进行下一次循环。

代码

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


public class Solution {
    /*
     * @param l1: The first list.
     * @param l2: The second list.
     * @return: the sum list of l1 and l2.
     */
    public ListNode addLists2(ListNode l1, ListNode l2) {
        // write your code here
        ListNode node=new ListNode(0);
        ListNode pre=node;
        int a=getLength(l1);
        int b=getLength(l2);
        if(a>b){
            node.next=l1;
            int temp=a-b;
            while(temp>0){
                if(l1.val!=9){
                    pre=l1;
                }
                temp--;
                l1=l1.next;
            }
            while(l1!=null){
                temp=l1.val+l2.val;
                if(temp>=10){
                    l1.val=temp%10;
                    pre.val=pre.val+1;
                    pre=pre.next;
                    while(true){
                        if(pre==l1){
                            break;
                        }
                        pre.val=0;
                        pre=pre.next;
                    }
                }else{
                    l1.val=temp;
                }
                if(l1.val!=9){
                    pre=l1;
                }
                l1=l1.next;
                l2=l2.next;
            }
            
        }else{
            node.next=l2;
            int temp=b-a;
            while(temp>0){
                if(l2.val!=9){
                    pre=l2;
                }
                temp--;
                l2=l2.next;
            }
            while(l2!=null){
                temp=l1.val+l2.val;
                if(temp>=10){
                    l2.val=temp%10;
                    pre.val=pre.val+1;
                    pre=pre.next;
                    while(true){
                        if(pre==l2){
                            break;
                        }
                        pre.val=0;
                        pre=pre.next;
                    }
                }else{
                    l2.val=temp;
                }
                if(l2.val!=9){
                    pre=l2;
                }
                l1=l1.next;
                l2=l2.next;
            }
        }
        if(node.val==0){
            return node.next;
        }else{
            return node;
        }
    }
    private int getLength(ListNode node){
        int i=0;
        while(node!=null){
            node=node.next;
            i++;
        }
        return i;
    }
}