Add Two Numbers Represented as Linked List in DSA C

Mental Model

We add two numbers digit by digit like how we add on paper, carrying over extra when sum is more than 9.

Analogy: Imagine adding two numbers written on paper from right to left, carrying over the tens to the next column.

List1: 2 -> 4 -> 3 -> null
List2: 5 -> 6 -> 4 -> null
Result: ?

Dry Run Walkthrough

Input: list1: 2->4->3, list2: 5->6->4

Goal: Add the two numbers represented by the lists and return the sum as a linked list

Step 1: Add first digits 2 + 5 = 7, no carry

Result: 7 -> null

Why: Start adding from the least significant digit

Step 2: Add second digits 4 + 6 = 10, carry 1

Result: 7 -> 0 -> null

Why: Sum is 10, so digit is 0 and carry 1 to next

Step 3: Add third digits 3 + 4 + carry 1 = 8, no carry

Result: 7 -> 0 -> 8 -> null

Why: Add carry to next digit sum

Result:

7 -> 0 -> 8 -> null

Annotated Code

DSA C

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

// Node structure for linked list
typedef struct Node {
    int val;
    struct Node* next;
} Node;

// Create new node
Node* newNode(int val) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->val = val;
    node->next = NULL;
    return node;
}

// Add two numbers represented by linked lists
Node* addTwoNumbers(Node* l1, Node* l2) {
    Node* dummy = newNode(0); // dummy head for result
    Node* curr = dummy;
    int carry = 0;

    while (l1 != NULL || l2 != NULL || carry != 0) {
        int x = (l1 != NULL) ? l1->val : 0;
        int y = (l2 != NULL) ? l2->val : 0;
        int sum = x + y + carry;
        carry = sum / 10; // carry for next digit
        curr->next = newNode(sum % 10); // digit for current place
        curr = curr->next; // move to next node

        if (l1 != NULL) l1 = l1->next; // advance l1
        if (l2 != NULL) l2 = l2->next; // advance l2
    }

    Node* result = dummy->next;
    free(dummy); // free dummy node
    return result;
}

// Print linked list
void printList(Node* head) {
    while (head != NULL) {
        printf("%d", head->val);
        if (head->next != NULL) printf(" -> ");
        head = head->next;
    }
    printf(" -> null\n");
}

int main() {
    // Create first number 2->4->3
    Node* l1 = newNode(2);
    l1->next = newNode(4);
    l1->next->next = newNode(3);

    // Create second number 5->6->4
    Node* l2 = newNode(5);
    l2->next = newNode(6);
    l2->next->next = newNode(4);

    Node* result = addTwoNumbers(l1, l2);
    printList(result);

    return 0;
}

while (l1 != NULL || l2 != NULL || carry != 0) {

continue adding while any list has digits or carry remains

int x = (l1 != NULL) ? l1->val : 0;

get current digit from l1 or 0 if none

int y = (l2 != NULL) ? l2->val : 0;

get current digit from l2 or 0 if none

int sum = x + y + carry;

sum digits and carry

carry = sum / 10;

calculate carry for next digit

curr->next = newNode(sum % 10);

create new node for current digit

curr = curr->next;

move current pointer forward

if (l1 != NULL) l1 = l1->next;

advance l1 pointer

if (l2 != NULL) l2 = l2->next;

advance l2 pointer

Output

7 -> 0 -> 8 -> null

Complexity Analysis

Time: O(n) because we traverse both linked lists once where n is the length of the longer list

Space: O(n) because the result linked list can be at most one node longer than the longer input list

vs Alternative: Compared to converting lists to numbers and back, this approach avoids large integer overflow and uses linear time and space

Edge Cases

One list is empty

The function returns the other list as the sum

DSA C

int x = (l1 != NULL) ? l1->val : 0;

Sum produces an extra carry digit

An extra node is added at the end for the carry

DSA C

while (l1 != NULL || l2 != NULL || carry != 0) {

Lists of different lengths

Shorter list digits are treated as 0 after end

DSA C

int y = (l2 != NULL) ? l2->val : 0;

When to Use This Pattern

When you see two linked lists representing numbers and need to add them digit by digit, use this pattern to simulate addition with carry.

Common Mistakes

Mistake: Not handling carry after both lists end
Fix: Include carry in while loop condition to add extra node if needed

Mistake: Advancing pointers without checking for NULL
Fix: Check if pointer is not NULL before advancing

Summary

Adds two numbers represented as linked lists digit by digit with carry.

Use when numbers are stored in reverse order in linked lists and you want their sum as a linked list.

The key insight is to add digits like on paper, carrying over tens to the next digit.