Add Two Numbers - Practice Coding Problems

Add Two Numbers - Problem

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Input & Output

Example 1 — Basic Addition

$ Input: l1 = [2,4,3], l2 = [5,6,4]

› Output: [7,0,8]

💡 Note: 342 + 465 = 807. The digits are stored in reverse order, so [2,4,3] represents 342, [5,6,4] represents 465, and the sum 807 is returned as [7,0,8].

Example 2 — Different Lengths

$ Input: l1 = [0], l2 = [0]

› Output: [0]

💡 Note: 0 + 0 = 0. The simplest case where both numbers are zero.

Example 3 — Carry Propagation

$ Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]

› Output: [8,9,9,9,0,0,0,1]

💡 Note: 9999999 + 9999 = 10009998. Shows how carries propagate through multiple digits, resulting in a longer output list.

Constraints

The number of nodes in each linked list is in the range [1, 100]
0 ≤ Node.val ≤ 9
It is guaranteed that the list represents a number that does not have leading zeros

Visualization

Tap to expand

Understanding the Visualization

Input Lists

Two linked lists: [2,4,3] = 342, [5,6,4] = 465

Addition Process

Add digit by digit: 2+5=7, 4+6=10 (carry 1), 3+4+1=8

Result List

Output [7,0,8] representing 807

Key Takeaway

🎯 Key Insight: Treat linked lists like numbers written backwards and add them digit by digit with carry handling

Asked in

a Amazon 85 M Microsoft 72 G Google 68 f Facebook 45

The key insight is to simulate manual addition digit by digit with carry propagation. The optimal approach uses a single pass to traverse both lists simultaneously, handling carries as we build the result. Time: O(max(m,n)), Space: O(max(m,n)).

Common Approaches

Approach	Time	Space	Notes
✓ Convert to Integer	O(max(m, n))	O(max(m, n))	Convert linked lists to integers, add them, then convert sum back to linked list
Single Pass with Carry	O(max(m, n))	O(max(m, n))	Traverse both lists simultaneously, adding digits with carry propagation

Convert to Integer — Algorithm Steps

Step 1: Traverse first linked list to extract number
Step 2: Traverse second linked list to extract number
Step 3: Add the two integers
Step 4: Convert sum back to linked list in reverse order

Visualization

Tap to expand

Step-by-Step Walkthrough

Extract Numbers

Convert [2,4,3] to 342 and [5,6,4] to 465

Add Integers

342 + 465 = 807

Build Result

Convert 807 back to [7,0,8]

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ListNode {
    int val;
    struct ListNode* next;
};

struct ListNode* solution(struct ListNode* l1, struct ListNode* l2) {
    long long num1 = listToNum(l1);
    long long num2 = listToNum(l2);
    long long total = num1 + num2;
    return numToList(total);
}

long long listToNum(struct ListNode* head) {
    long long num = 0;
    long long multiplier = 1;
    while (head) {
        num += head->val * multiplier;
        multiplier *= 10;
        head = head->next;
    }
    return num;
}

struct ListNode* numToList(long long num) {
    if (num == 0) {
        struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
        node->val = 0;
        node->next = NULL;
        return node;
    }
    
    struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* current = dummy;
    while (num > 0) {
        int digit = num % 10;
        current->next = (struct ListNode*)malloc(sizeof(struct ListNode));
        current->next->val = digit;
        current->next->next = NULL;
        current = current->next;
        num /= 10;
    }
    return dummy->next;
}

struct ListNode* arrayToList(int* arr, int size) {
    if (size == 0) return NULL;
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->val = arr[0];
    head->next = NULL;
    struct ListNode* current = head;
    for (int i = 1; i < size; i++) {
        current->next = (struct ListNode*)malloc(sizeof(struct ListNode));
        current->next->val = arr[i];
        current->next->next = NULL;
        current = current->next;
    }
    return head;
}

void printList(struct ListNode* head) {
    printf("[");
    int first = 1;
    while (head) {
        if (!first) printf(",");
        printf("%d", head->val);
        first = 0;
        head = head->next;
    }
    printf("]\n");
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse first array
    int arr1[100], size1 = 0;
    char* ptr = strchr(line, '[');
    ptr++;
    char* token = strtok(ptr, ",]");
    while (token != NULL) {
        arr1[size1++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    fgets(line, sizeof(line), stdin);
    
    // Parse second array
    int arr2[100], size2 = 0;
    ptr = strchr(line, '[');
    ptr++;
    token = strtok(ptr, ",]");
    while (token != NULL) {
        arr2[size2++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    struct ListNode* l1 = arrayToList(arr1, size1);
    struct ListNode* l2 = arrayToList(arr2, size2);
    
    struct ListNode* result = solution(l1, l2);
    printList(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(max(m, n))

Two passes to extract numbers plus one pass to build result, where m and n are lengths of input lists

✓ Linear Growth

Space Complexity

O(max(m, n))

New linked list to store the result

⚡ Linearithmic Space

666.0K Views

Very High Frequency

~25 min Avg. Time

18.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Convert to Integer — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler