Add two numbers as LL

Given two non-empty linked lists l1 and l2 which represent two non-negative integers.

The digits are stored in reverse order with each node storing one digit. Add two numbers and return the sum as a linked list.

• The sum Linked List will be in reverse order as well.
• The Two given Linked Lists represent numbers without any leading zeros, except when the number is zero itself.

Using Dummy Node#

Simulate grade-school addition digit by digit. Because the numbers are stored in reverse order, the first nodes of the lists are already the least-significant digits — exactly what you want to add first. At each step add the two current digits plus any carry from the previous step, append sum % 10 as a new node to the result list, and set carry = sum / 10. Continue while either list still has nodes; handle a final carry by appending one more node after the loop. The dummy sentinel node simplifies list construction by avoiding a special case for the first node.

/*
Definition of singly linked list:
struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int data1)
    {
        val = data1;
        next = NULL;
    }
    ListNode(int data1, ListNode *next1)
    {
        val = data1;
        next = next1;
    }
};
*/

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummyHead = new ListNode(-1);
        ListNode* tailPointer = dummyHead;

        int carry = 0;
        while(l1 || l2){
            int num1 = l1 ? l1->val : 0;
            int num2 = l2 ? l2->val : 0;

            int sum = num1 + num2 + carry;
            carry = sum/10;

            ListNode* curr = new ListNode(sum%10);
            tailPointer->next = curr;
            tailPointer = tailPointer->next;

            if(l1)
                l1 = l1->next;
            if(l2)
                l2 = l2->next;
        }
        if(carry){
            ListNode* curr = new ListNode(carry);
            tailPointer->next = curr;
            tailPointer = tailPointer->next;
        }

        return dummyHead->next;
    }
};

Time Complexity:O(max(m,n)), where m and n are the lengths of the two linked lists.

Space Complexity:O(max(m,n)), where m and n are the lengths of the two linked lists, due to the creation of a new linked list to store the result.

Follow Up#

How would your approach change if the digits were stored in forward order instead of reverse order?#

When digits are in forward order, the most-significant digit is at the head — so you can no longer process nodes left-to-right and add them directly (you'd be adding the wrong place values).

Two clean strategies:

1. Reverse both lists first
Reverse l1 and l2, then run the exact same dummy-node algorithm above, and finally reverse the result list before returning. Simple reuse of existing logic; just three passes.

2. Use a stack
Push all nodes of l1 onto one stack and all nodes of l2 onto another. Pop from both stacks simultaneously — each pop gives the least-significant digit next — and build the result list by prepending new nodes (so the final list is already in forward order without a reversal step).

ListNode* addTwoNumbersForward(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 carry = 0;
    ListNode* head = nullptr;   // build result in forward order by prepending

    while (!s1.empty() || !s2.empty() || carry) {
        int num1 = 0, num2 = 0;
        if (!s1.empty()) { num1 = s1.top(); s1.pop(); }
        if (!s2.empty()) { num2 = s2.top(); s2.pop(); }

        int sum = num1 + num2 + carry;
        carry = sum / 10;

        ListNode* node = new ListNode(sum % 10);
        node->next = head;   // prepend → result list is forward-ordered
        head = node;
    }
    return head;
}

The stack approach avoids mutating the input lists and skips the final reversal pass, keeping Time and Space both O(m + n).