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.

Practice

1. What does the problem "Add Two Numbers Represented as Linked List" mean?
Each node contains a single digit and digits are stored in reverse order. What is the goal?

easy

A. Reverse both linked lists and then add the digits.

B. Multiply the two numbers and return the product as a linked list.

C. Add the two numbers digit by digit and return the sum as a linked list in reverse order.

D. Sort the linked lists before adding.

Solution

1. Step 1: Understand the representation of numbers in linked lists

   Each linked list node holds one digit, and the digits are stored in reverse order, meaning the first node is the ones place.

2. Step 2: Define the goal of the problem

   The goal is to add these two numbers digit by digit, handling any carry, and return the result as a new linked list in the same reverse order format.

3. Final Answer:

   Add the two numbers digit by digit and return the sum as a linked list in reverse order. -> Option C

4. Quick Check:

   Adding reversed digit lists = sum list reversed [OK]

Hint: Add digits node-wise with carry, keep result reversed [OK]

Common Mistakes:

• Trying to add numbers as integers directly
• Ignoring carry between digits
• Not returning the result in reverse order

2. Which of the following is the correct way to declare a node structure for a singly linked list in C for this problem?

easy

A. struct Node { int val; struct Node* prev; };

B. struct Node { int val; Node* next; };

C. struct Node { int val; struct Node next; };

D. struct Node { int val; struct Node* next; };

Solution

1. Step 1: Understand C struct syntax for linked list nodes

   In C, to define a node with an integer value and pointer to next node, use 'struct Node* next;'.

2. Step 2: Identify correct pointer usage

   struct Node { int val; struct Node* next; }; correctly uses 'struct Node* next;' which is the pointer to the next node. struct Node { int val; Node* next; }; misses 'struct' keyword, C uses struct Node instead of pointer, D uses 'prev' which is for doubly linked list.

3. Final Answer:

   struct Node { int val; struct Node* next; }; -> Option D

4. Quick Check:

   Pointer to next node = struct Node* next [OK]

Hint: Use 'struct Node* next;' for next pointer in C struct [OK]

Common Mistakes:

• Omitting 'struct' keyword before Node*
• Using struct Node instead of pointer for next
• Confusing singly linked list with doubly linked list

3. What is the output linked list after adding the two numbers represented by these linked lists?
List1: 2 -> 4 -> 3 -> null (represents 342)
List2: 5 -> 6 -> 4 -> null (represents 465)
Code snippet adds digits with carry:

medium

A. 7 -> 0 -> 8 -> null

B. 8 -> 0 -> 7 -> null

C. 7 -> 10 -> 7 -> null

D. 7 -> 0 -> 7 -> null

Solution

1. Step 1: Add digits node by node with carry

   2+5=7 (carry 0), 4+6=10 (carry 1), 3+4+1=8 (carry 0)

2. Step 2: Form the resulting linked list

   Digits are 7 (ones), 0 (tens), 8 (hundreds), so linked list is 7 -> 0 -> 8 -> null.

3. Final Answer:

   7 -> 0 -> 8 -> null -> Option A

4. Quick Check:

   342 + 465 = 807 reversed = 7->0->8 [OK]

Hint: Add digits with carry, store remainder, move forward [OK]

Common Mistakes:

• Not handling carry correctly
• Adding digits without carry from previous sum
• Confusing order of digits in output

4. Given this buggy code snippet for adding two linked lists, what is the main error?

while(l1 != NULL || l2 != NULL) {
  int sum = carry;
  if(l1 != NULL) { sum += l1->val; l1 = l1->next; }
  if(l2 != NULL) { sum += l2->val; l2 = l2->next; }
  carry = sum / 10;
  sum = sum % 10;
  newNode->val = sum;
  newNode = newNode->next;
}

medium

A. newNode->next is not initialized before assignment, causing undefined behavior.

B. Carry is not updated correctly after sum calculation.

C. Loop condition should be && instead of ||.

D. Sum should be reset to zero inside the loop.

Solution

1. Step 1: Analyze pointer usage for newNode

   The code assigns newNode->val but then moves newNode to newNode->next without initializing newNode->next, so newNode->next is likely NULL or garbage.

2. Step 2: Identify missing node creation

   Before moving newNode = newNode->next, a new node must be created and linked to newNode->next to avoid undefined behavior.

3. Final Answer:

   newNode->next is not initialized before assignment, causing undefined behavior. -> Option A

4. Quick Check:

   Always create new node before moving pointer [OK]

Hint: Always allocate new node before moving next pointer [OK]

Common Mistakes:

• Not creating new nodes for the result list
• Incorrect loop condition causing missed nodes
• Incorrect carry update logic

5. You have two linked lists representing numbers in reverse order:
List1: 9 -> 9 -> 9 -> 9 -> null (represents 9999)
List2: 1 -> null (represents 1)
What is the correct resulting linked list after adding these two numbers?

hard

A. 9 -> 9 -> 9 -> 9 -> 1 -> null

B. 0 -> 0 -> 0 -> 0 -> 1 -> null

C. 1 -> 0 -> 0 -> 0 -> 0 -> null

D. 0 -> 0 -> 0 -> 0 -> null

Solution

1. Step 1: Add digits with carry step-by-step

   9+1=10 (digit 0, carry 1), next 9+0+1=10 (digit 0, carry 1), repeat for next two 9s similarly.

2. Step 2: Handle final carry

   After last digit, carry is 1, so add new node with value 1 at the end.

3. Final Answer:

   0 -> 0 -> 0 -> 0 -> 1 -> null -> Option B

4. Quick Check:

   9999 + 1 = 10000 reversed = 0->0->0->0->1 [OK]

Hint: Add carry after last nodes if non-zero [OK]

Common Mistakes:

• Forgetting to add final carry node
• Stopping addition early when one list ends
• Misplacing the carry digit in the result