Add Two Numbers Represented as Linked List in DSA C++

Mental Model

We add two numbers digit by digit from the front of two linked lists, carrying over when sums exceed 9.

Analogy: Like adding two numbers on paper from right to left, but here each digit is a node in a chain, and we move along both chains together.

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

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 first nodes, sum is less than 10 so no carry

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

Result: 7 -> 0 -> null, carry = 1

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

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

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

Why: Sum is 8, no carry left, addition complete

Result:

7 -> 0 -> 8 -> null

Annotated Code

DSA C++

#include <iostream>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(0); // dummy head for result
        ListNode* curr = dummy;
        int carry = 0;
        while (l1 != nullptr || l2 != nullptr || carry != 0) {
            int sum = carry;
            if (l1 != nullptr) {
                sum += l1->val; // add l1 digit
                l1 = l1->next; // move l1 forward
            }
            if (l2 != nullptr) {
                sum += l2->val; // add l2 digit
                l2 = l2->next; // move l2 forward
            }
            carry = sum / 10; // update carry
            curr->next = new ListNode(sum % 10); // create new node with digit
            curr = curr->next; // move curr forward
        }
        return dummy->next; // skip dummy head
    }
};

void printList(ListNode* head) {
    while (head != nullptr) {
        std::cout << head->val;
        if (head->next != nullptr) std::cout << " -> ";
        head = head->next;
    }
    std::cout << " -> null" << std::endl;
}

int main() {
    // Create first list 2 -> 4 -> 3
    ListNode* l1 = new ListNode(2);
    l1->next = new ListNode(4);
    l1->next->next = new ListNode(3);

    // Create second list 5 -> 6 -> 4
    ListNode* l2 = new ListNode(5);
    l2->next = new ListNode(6);
    l2->next->next = new ListNode(4);

    Solution sol;
    ListNode* result = sol.addTwoNumbers(l1, l2);
    printList(result);
    return 0;
}

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

continue adding while any list has digits or carry remains

sum += l1->val; // add l1 digit

add current digit from first list

l1 = l1->next; // move l1 forward

advance pointer in first list

sum += l2->val; // add l2 digit

add current digit from second list

l2 = l2->next; // move l2 forward

advance pointer in second list

carry = sum / 10; // update carry

calculate carry for next digit

curr->next = new ListNode(sum % 10); // create new node with digit

create new node with current digit of sum

curr = curr->next; // move curr forward

advance pointer in result list

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 list can be at most one node longer than the longer input list

vs Alternative: Compared to converting lists to numbers and adding, this method avoids large integer conversion and handles very long numbers efficiently

Edge Cases

One list is empty

Returns the other list as the sum

DSA C++

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

Sum produces an extra carry digit

Adds an extra node at the end for the carry

DSA C++

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

Lists of different lengths

Continues adding remaining digits of longer list with carry

DSA C++

if (l1 != nullptr) { sum += l1->val; l1 = l1->next; }

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 handle carry and different lengths cleanly.

Common Mistakes

Mistake: Not handling the final carry after both lists are processed
Fix: Include carry in the while loop condition to add an extra node if needed

Mistake: Advancing pointers before adding their values
Fix: Add values first, then move pointers forward

Summary

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

Use when adding large numbers stored in linked lists where digits are nodes.

The key insight is to add corresponding digits and carry while traversing both lists simultaneously.

Practice

1. What does the problem "Add Two Numbers Represented as Linked List" mainly involve?

easy

A. Adding two numbers where each digit is stored in a node of a linked list

B. Sorting two linked lists in ascending order

C. Finding the middle node of a linked list

D. Reversing a linked list

Solution

1. Step 1: Understand the problem context

   The problem involves two linked lists where each node contains a single digit of a number, stored in reverse order.

2. Step 2: Identify the required operation

   We need to add these two numbers digit by digit, handling carry, and return the sum as a linked list.

3. Final Answer:

   Adding two numbers where each digit is stored in a node of a linked list -> Option A

4. Quick Check:

   Adding digits in linked lists = Adding two numbers where each digit is stored in a node of a linked list [OK]

Hint: Think of linked list nodes as digits of a number [OK]

Common Mistakes:

• Confusing addition with sorting
• Thinking the problem is about reversing lists
• Assuming the digits are stored in normal order

2. Which of the following C++ code snippets correctly declares a node structure for a singly linked list used in this problem (using nullptr)?

easy

A. struct Node { int val; Node* next; Node(int x) : val(x), next(NULL) {} };

B. struct Node { int val; Node next; Node(int x) : val(x), next(nullptr) {} };

C. struct Node { int val; Node* next; Node(int x) : val(x), next(nullptr) {} };

D. struct Node { int val; Node* next; Node(int x) { val = x; next = NULL; } };

Solution

1. Step 1: Check pointer usage in struct

   Node* next is correct to point to the next node; struct Node { int val; Node next; Node(int x) : val(x), next(nullptr) {} }; uses Node next which is incorrect (causes infinite recursion).

2. Step 2: Check constructor initialization

   struct Node { int val; Node* next; Node(int x) : val(x), next(nullptr) {} }; uses member initializer list correctly with nullptr; struct Node { int val; Node* next; Node(int x) { val = x; next = NULL; } }; uses assignment inside constructor body which is valid but less modern; struct Node { int val; Node* next; Node(int x) : val(x), next(NULL) {} }; uses NULL which is legacy.

3. Final Answer:

   struct Node { int val; Node* next; Node(int x) : val(x), next(nullptr) {} }; -> Option C

4. Quick Check:

   Use pointer and nullptr in constructor [OK]

Hint: Use Node* next and initialize with nullptr [OK]

Common Mistakes:

• Using Node next instead of Node* next
• Using NULL instead of nullptr
• Not initializing next pointer

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) Choose the correct resulting linked list:

medium

A. 7 -> 10 -> 7 -> null

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

C. 8 -> 0 -> 7 -> null

D. 7 -> 1 -> 8 -> 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, 0 (from 10 carry), 8 so list is 7 -> 0 -> 8 -> null

3. Final Answer:

   7 -> 0 -> 8 -> null -> Option B

4. Quick Check:

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

Hint: Add digits with carry, store remainder in node [OK]

Common Mistakes:

• Not handling carry correctly
• Adding digits in wrong order
• Confusing node values with actual numbers

4. Consider the following code snippet for adding two numbers represented as linked lists. What is the error?

Node* addTwoNumbers(Node* l1, Node* l2) {
  Node* dummy = new Node(0);
  Node* current = dummy;
  int carry = 0;
  while (l1 != nullptr && l2 != nullptr) {
    int sum = l1->val + l2->val + carry;
    carry = sum / 10;
    current->next = new Node(sum % 10);
    current = current->next;
    l1 = l1->next;
    l2 = l2->next;
  }
  return dummy->next;
}

medium

A. The loop condition should be while (l1 != nullptr || l2 != nullptr)

B. Carry is not updated correctly

C. Dummy node should be deleted before return

D. The sum calculation is incorrect

Solution

1. Step 1: Analyze loop condition

   The loop runs only while both l1 and l2 are not null, so it stops early if one list is longer.

2. Step 2: Correct loop condition

   It should continue while either l1 or l2 has nodes to process all digits, so use || instead of &&.

3. Final Answer:

   The loop condition should be while (l1 != nullptr || l2 != nullptr) -> Option A

4. Quick Check:

   Use || to handle different length lists [OK]

Hint: Use || in loop to cover all nodes [OK]

Common Mistakes:

• Using && causes missing nodes in longer list
• Ignoring carry after loop ends
• Not advancing pointers correctly

5. Given two linked lists representing numbers in reverse order, how would you modify the addition algorithm to handle the case when the final carry is non-zero after processing all nodes? Choose the best approach:

hard

A. Ignore the carry since it is not needed

B. Subtract the carry from the last node value

C. Restart the addition from the beginning

D. Add a new node with the carry value at the end of the result list

Solution

1. Step 1: Understand carry after full addition

   After adding all nodes, if carry is still 1, it means the sum has an extra digit.

2. Step 2: Add new node for carry

   To represent this extra digit, create a new node with carry value and link it at the end.

3. Final Answer:

   Add a new node with the carry value at the end of the result list -> Option D

4. Quick Check:

   Carry leftover means add new node [OK]

Hint: Add carry node if leftover after loop ends [OK]

Common Mistakes:

• Ignoring leftover carry causing wrong sum
• Trying to subtract carry instead of adding node
• Restarting addition unnecessarily