Add Two Numbers Represented as Linked List in DSA C - Build from Scratch

Add Two Numbers Represented as Linked List

📖 Scenario: You are working on a simple calculator app that adds two numbers. These numbers are stored in reverse order in linked lists, where each node contains a single digit. Your task is to add these two numbers and return the sum as a linked list in the same reversed order.

🎯 Goal: Build a program that creates two linked lists representing numbers, adds them digit by digit, and prints the resulting linked list showing the sum.

📋 What You'll Learn

Create two linked lists representing the numbers 342 and 465 in reverse order

Create a variable to hold the carry during addition

Write the logic to add the two numbers digit by digit using linked lists

Print the resulting linked list showing the sum

💡 Why This Matters

🌍 Real World

Adding large numbers digit by digit is useful in calculators and financial software where numbers can be very large and stored as linked lists.

💼 Career

Understanding linked list operations and digit-wise addition is important for software engineers working on low-level data manipulation, embedded systems, or interview coding challenges.

1

Create two linked lists representing numbers

Create a linked list node struct called Node with an int data and a Node* next. Then create two linked lists called l1 and l2 representing the numbers 342 and 465 in reverse order. For l1, create nodes with data 2, 4, 3. For l2, create nodes with data 5, 6, 4. Link the nodes properly.

DSA C

// Define struct Node
// Create linked list l1 with nodes 2 -> 4 -> 3
// Create linked list l2 with nodes 5 -> 6 -> 4
// Your code here

Hint

Remember to create each node with malloc and set the data and next fields properly.

2

Create a carry variable for addition

Create an integer variable called carry and set it to 0. Also create a pointer Node* result initialized to NULL to hold the result linked list. Create a pointer Node* tail initialized to NULL to track the last node in the result list.

DSA C

#include 
#include 

typedef struct Node {
    int data;
    struct Node* next;
} Node;

int main() {
    Node* l1 = malloc(sizeof(Node));
    l1->data = 2;
    l1->next = malloc(sizeof(Node));
    l1->next->data = 4;
    l1->next->next = malloc(sizeof(Node));
    l1->next->next->data = 3;
    l1->next->next->next = NULL;

    Node* l2 = malloc(sizeof(Node));
    l2->data = 5;
    l2->next = malloc(sizeof(Node));
    l2->next->data = 6;
    l2->next->next = malloc(sizeof(Node));
    l2->next->next->data = 4;
    l2->next->next->next = NULL;

    // Create carry and result pointers
    // Your code here

    return 0;
}

Hint

Use int carry = 0; and initialize Node* result = NULL; and Node* tail = NULL;.

3

Add the two numbers digit by digit

Write a while loop that continues as long as l1 is not NULL or l2 is not NULL or carry is not zero. Inside the loop, get the digit from l1 and l2 if they are not NULL, else use 0. Calculate the sum of these digits plus carry. Update carry to sum divided by 10. Create a new node with data equal to sum modulo 10. Append this new node to the result linked list. Move l1 and l2 to their next nodes if they are not NULL.

DSA C

#include 
#include 

typedef struct Node {
    int data;
    struct Node* next;
} Node;

int main() {
    Node* l1 = malloc(sizeof(Node));
    l1->data = 2;
    l1->next = malloc(sizeof(Node));
    l1->next->data = 4;
    l1->next->next = malloc(sizeof(Node));
    l1->next->next->data = 3;
    l1->next->next->next = NULL;

    Node* l2 = malloc(sizeof(Node));
    l2->data = 5;
    l2->next = malloc(sizeof(Node));
    l2->next->data = 6;
    l2->next->next = malloc(sizeof(Node));
    l2->next->next->data = 4;
    l2->next->next->next = NULL;

    int carry = 0;
    Node* result = NULL;
    Node* tail = NULL;

    // Add digits and create result linked list
    // Your code here

    return 0;
}

Hint

Use a loop to add digits and carry. Create new nodes for the sum digits and link them to the result list.

4

Print the resulting linked list

Write a Node* pointer called current and set it to result. Use a while loop to traverse the result linked list. Inside the loop, print the data of the current node followed by -> . Move current to the next node. After the loop, print null to indicate the end of the list.

DSA C

#include 
#include 

typedef struct Node {
    int data;
    struct Node* next;
} Node;

int main() {
    Node* l1 = malloc(sizeof(Node));
    l1->data = 2;
    l1->next = malloc(sizeof(Node));
    l1->next->data = 4;
    l1->next->next = malloc(sizeof(Node));
    l1->next->next->data = 3;
    l1->next->next->next = NULL;

    Node* l2 = malloc(sizeof(Node));
    l2->data = 5;
    l2->next = malloc(sizeof(Node));
    l2->next->data = 6;
    l2->next->next = malloc(sizeof(Node));
    l2->next->next->data = 4;
    l2->next->next->next = NULL;

    int carry = 0;
    Node* result = NULL;
    Node* tail = NULL;

    while (l1 != NULL || l2 != NULL || carry != 0) {
        int val1 = (l1 != NULL) ? l1->data : 0;
        int val2 = (l2 != NULL) ? l2->data : 0;
        int sum = val1 + val2 + carry;
        carry = sum / 10;
        Node* newNode = malloc(sizeof(Node));
        newNode->data = sum % 10;
        newNode->next = NULL;

        if (result == NULL) {
            result = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }

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

    // Print the result linked list
    // Your code here

    return 0;
}

Hint

Traverse the result linked list and print each node's data followed by ' -> '. After the loop, print 'null'.

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