Question

Formatted question description: https://leetcode.ca/all/445.html

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

Algorithm

This question is an extension of the previous Add Two Numbers. We can see that the highest position of this question is at the top of the linked list. If we flip the linked list, it will be the same as the previous question.

Here we look at some unmodified ones. The method of linked list order. Since addition needs to start from the lowest bit, and the lowest bit is at the end of the linked list, the linked list can only be traversed from the front to the back, and the previous elements cannot be retrieved.

What should I do? We can use the stack to store all the elements, and then use the last-in-first-out feature of the stack to fetch numbers from back to front.

We first traverse the two linked lists and push all the numbers into the two stacks s1 and s2. We create a res node with a value of 0, and then start the loop. If the stack is not empty, add the top number of the stack to sum, then assign the res node value to sum%10, and then create a new carry node head, and assign it to sum /10, if there is no carry, then it is 0, and then we connect res after the head, and point res to head, so that after the loop exits, we only need to see if the value of res is 0, if it is 0, return res->next, not 0 Just return res, see the code as follows:

Code

C++

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        stack<int> s1, s2;
        while (l1) {
            s1.push(l1->val);
            l1 = l1->next;
        }
        while (l2) {
            s2.push(l2->val);
            l2 = l2->next;
        }
        int sum = 0;
        ListNode *res = new ListNode(0);
        while (!s1.empty() || !s2.empty()) {
            if (!s1.empty()) {sum += s1.top(); s1.pop();}
            if (!s2.empty()) {sum += s2.top(); s2.pop();}
            res->val = sum % 10;
            ListNode *head = new ListNode(sum / 10);
            head->next = res;
            res = head;
            sum /= 10;
        }
        return res->val == 0 ? res->next : res;
    }
};

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<ListNode> stack1 = new Stack<ListNode>();
        Stack<ListNode> stack2 = new Stack<ListNode>();
        ListNode temp1 = l1, temp2 = l2;
        while (temp1 != null) {
            stack1.push(temp1);
            temp1 = temp1.next;
        }
        while (temp2 != null) {
            stack2.push(temp2);
            temp2 = temp2.next;
        }
        Stack<ListNode> stackSum = new Stack<ListNode>();
        int carry = 0;
        while (!stack1.isEmpty() && !stack2.isEmpty()) {
            ListNode node1 = stack1.pop(), node2 = stack2.pop();
            int curVal = carry + node1.val + node2.val;
            carry = curVal / 10;
            curVal %= 10;
            ListNode nodeSum = new ListNode(curVal);
            if (!stackSum.isEmpty())
                nodeSum.next = stackSum.peek();
            stackSum.push(nodeSum);
        }
        while (!stack1.isEmpty()) {
            ListNode node1 = stack1.pop();
            int curVal = carry + node1.val;
            carry = curVal / 10;
            curVal %= 10;
            ListNode nodeSum = new ListNode(curVal);
            if (!stackSum.isEmpty())
                nodeSum.next = stackSum.peek();
            stackSum.push(nodeSum);
        }
        while (!stack2.isEmpty()) {
            ListNode node2 = stack2.pop();
            int curVal = carry + node2.val;
            carry = curVal / 10;
            curVal %= 10;
            ListNode nodeSum = new ListNode(curVal);
            if (!stackSum.isEmpty())
                nodeSum.next = stackSum.peek();
            stackSum.push(nodeSum);
        }
        while (carry > 0) {
            int curVal = carry % 10;
            carry /= 10;
            ListNode curNode = new ListNode(curVal);
            if (!stackSum.isEmpty())
                curNode.next = stackSum.peek();
            stackSum.push(curNode);
        }
        return stackSum.peek();
    }
}

All Problems

All Solutions