Add Two Numbers Represented as Linked List in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Adding Two Linked Lists Representing Numbers

What is the printed linked list after adding these two numbers represented by linked lists?

List 1: 2 -> 4 -> 3 -> null (represents 342)
List 2: 5 -> 6 -> 4 -> null (represents 465)

Code adds the numbers and prints the resulting linked list.

DSA C

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

struct Node* addTwoNumbers(struct Node* l1, struct Node* l2) {
    struct Node* dummy = malloc(sizeof(struct Node));
    dummy->val = 0;
    dummy->next = NULL;
    struct Node* current = dummy;
    int carry = 0;
    while (l1 != NULL || l2 != NULL || carry != 0) {
        int sum = carry;
        if (l1 != NULL) {
            sum += l1->val;
            l1 = l1->next;
        }
        if (l2 != NULL) {
            sum += l2->val;
            l2 = l2->next;
        }
        carry = sum / 10;
        struct Node* newNode = malloc(sizeof(struct Node));
        newNode->val = sum % 10;
        newNode->next = NULL;
        current->next = newNode;
        current = newNode;
    }
    struct Node* result = dummy->next;
    free(dummy);
    return result;
}

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

// After calling addTwoNumbers with above lists, printList is called on result.

A 7 -> 0 -> 8 -> null

B 8 -> 0 -> 7 -> null

C 7 -> 10 -> 7 -> null

D 5 -> 10 -> 7 -> null

💡 Hint

Add digits from right to left, carry over if sum >= 10.

The numbers 342 + 465 = 807. The linked list stores digits in reverse order: 7 -> 0 -> 8 -> null.

🧠 Conceptual

intermediate

Understanding Carry in Linked List Addition

Why is it necessary to continue the loop when carry is not zero after processing both linked lists?

A Because carry indicates the end of the linked list.

B Because carry resets the linked list pointers to start.

C Because carry might add an extra digit to the result linked list.

D Because carry stores the sum of all digits processed so far.

💡 Hint

Think about what happens if the last sum is 15.

If the last addition results in a carry (like 1), it means an extra digit must be added to the result linked list to represent that carry.

🔧 Debug

advanced

Identify the Bug in Linked List Addition Code

What error will this code cause when adding two linked lists?

Code snippet:
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; struct Node* newNode = malloc(sizeof(struct Node)); newNode->val = sum % 10; newNode->next = NULL; current->next = newNode; current = newNode; } // Missing carry check after loop

A Memory leak due to missing free calls.

B The last carry digit is lost, resulting in incorrect sum.

C Segmentation fault due to null pointer dereference.

D Infinite loop because loop condition never ends.

💡 Hint

What if the last sum is 15?

If carry is not zero after loop ends, it must be added as a new node. Missing this causes wrong result.

❓ Predict Output

advanced

Output of Adding Unequal Length Linked Lists

What is the output linked list after adding these two numbers?

List 1: 9 -> 9 -> 9 -> 9 -> null (represents 9999)
List 2: 1 -> null (represents 1)

Use the standard addition code with carry.

A 9 -> 9 -> 9 -> 10 -> null

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

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

D 0 -> 0 -> 0 -> 0 -> 1 -> null

💡 Hint

Add digit by digit with carry, note length difference.

9999 + 1 = 10000, represented as 0->0->0->0->1->null in reverse order.

🚀 Application

expert

Calculate Length of Result Linked List After Addition

Given two linked lists representing numbers, what is the maximum possible length of the resulting linked list after addition?

A Maximum length is max(length of list1, length of list2) + 1

B Maximum length is sum of lengths of list1 and list2

C Maximum length is max(length of list1, length of list2)

D Maximum length is min(length of list1, length of list2) + 1

💡 Hint

Consider carry from the last digit addition.

Adding two numbers can produce a carry that adds one extra digit beyond the longer list length.

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