LintCode - 链表求和II（中等）

版权声明：本文为博主原创文章，未经博主允许不得转载。

难度：中等

要求：

你有两个用链表代表的整数，其中每个节点包含一个数字。数字存储按照在原来整数中相反
的顺序，使得第一个数字位于链表的开头。写出一个函数将两个整数相加，用链表形式返回和。

样例

给出 6->1->7 + 2->9->5。即，617 + 295。
返回 9->1->2。即，912 。

思路：

解题容易，注意边界处理。

/**
 * 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) {
        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }
        
        //
        Stack<Integer> s = new Stack<Integer>();
        Stack<ListNode> s1 = new Stack<ListNode>();
        Stack<ListNode> s2 = new Stack<ListNode>();
        
        //进位
        int c = 0;
        
        while(l1 != null){
            s1.add(l1);
            l1 = l1.next;
        }
        
        while(l2 != null){
            s2.add(l2);
            l2 = l2.next;
        }
        
        while(!s1.isEmpty() || !s2.isEmpty() || c != 0){
            int n1 = 0;
            if(!s1.isEmpty()){
                n1 = s1.pop().val;
            }
            
            int n2 = 0;
            if(!s2.isEmpty()){
                n2 = s2.pop().val;
            }
            
            int result = n1 + n2 + c;
            if(result >= 10){
                c =  result / 10;
                result %= 10;
            }else{
                c = 0;
            }
            s.add(result);
        }
        
        ListNode root = null;
        ListNode node = null;
        
        while(!s.isEmpty()){
            int val = s.pop();
            if(root == null){
                root = new ListNode(val);
                node = root;
            }else{
                node.next = new ListNode(val);
                node = node.next;
            }
        }
        return root;
    }
}

总耗时: 1988 ms