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
2. Add Two Numbers 的变形，之前的题最高位在链表末位，此题链表头部表示高位，尾部表示低位，不允许反转链表。两个数相加需要从低位开始。可以利用Stack的特点后进先出，遍历两个链表，将数字分别压入两个栈s1和s2，然后开始循环，如果栈不为空，则将栈顶数字加入sum中。
Java:
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<Integer> s1 = new Stack<Integer>();
Stack<Integer> s2 = new Stack<Integer>();
while(l1 != null) {
s1.push(l1.val);
l1 = l1.next;
};
while(l2 != null) {
s2.push(l2.val);
l2 = l2.next;
}
int sum = 0;
ListNode list = new ListNode(0);
while (!s1.empty() || !s2.empty()) {
if (!s1.empty()) sum += s1.pop();
if (!s2.empty()) sum += s2.pop();
list.val = sum % 10;
ListNode head = new ListNode(sum / 10);
head.next = list;
list = head;
sum /= 10;
}
return list.val == 0 ? list.next : list;
}
}
Python:
class Solution(object):
def addTwoNumbers(self, l1, l2):
stk1, stk2 = [], []
while l1:
stk1.append(l1.val)
l1 = l1.next
while l2:
stk2.append(l2.val)
l2 = l2.next prev, head = None, None
sum = 0
while stk1 or stk2:
sum /= 10
if stk1:
sum += stk1.pop()
if stk2:
sum += stk2.pop() head = ListNode(sum % 10)
head.next = prev
prev = head if sum >= 10:
head = ListNode(sum / 10)
head.next = prev return head
C++:
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
stack<int> stk1, stk2;
while (l1) {
stk1.emplace(l1->val);
l1 = l1->next;
}
while (l2) {
stk2.emplace(l2->val);
l2 = l2->next;
}
ListNode *prev = nullptr, *head = nullptr;
int sum = 0;
while (!stk1.empty() || !stk2.empty()) {
sum /= 10;
if (!stk1.empty()) {
sum += stk1.top();
stk1.pop();
}
if (!stk2.empty()) {
sum += stk2.top();
stk2.pop();
}
head = new ListNode(sum % 10);
head->next = prev;
prev = head;
}
if (sum >= 10) {
head = new ListNode(sum / 10);
head->next = prev;
}
return head;
}
};
相似题目：
[LeetCode] 2. Add Two Numbers 两个数字相加