You are given two linked lists representing two non-negative numbers.
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
The key of this problem is to think of using Stack
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<ListNode> st1 = new Stack<ListNode>();
Stack<ListNode> st2 = new Stack<ListNode>();
while (l1 != null) {
st1.push(l1);
l1 = l1.next;
}
while (l2 != null) {
st2.push(l2);
l2 = l2.next;
}
ListNode dummy = new ListNode(-1);
int carry = 0;
while (st1.size()!=0 || st2.size()!=0 || carry!=0) {
int sum = 0;
if (st1.size() != 0) sum += st1.pop().val;
if (st2.size() != 0) sum += st2.pop().val;
if (carry != 0) sum += carry;
ListNode newNode = new ListNode(sum%10);
newNode.next = dummy.next;
dummy.next = newNode;
carry = sum / 10;
}
return dummy.next;
}
}
原文：http://www.cnblogs.com/apanda009/p/7376266.html