Add Two Numbers Represented as Linked List in DSA C++ - Execution Trace

Concept Flow - Add Two Numbers Represented as Linked List

Start at head of List1 and List2

↓

Add digits + carry

↓

Create new node with sum % 10

↓

Move pointers to next nodes

↓

Carry = sum / 10

↓

Are both lists and carry empty?

No→Repeat addition

Yes↓

Done: Return result list

We add digits from both lists node by node, carry over extra, create new nodes for sum digits, and continue until all digits and carry are processed.

Execution Sample

DSA C++

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
  int carry = 0;
  ListNode* dummy = new ListNode(0);
  ListNode* current = dummy;
  while (l1 || l2 || carry) {
    int sum = carry + (l1 ? l1->val : 0) + (l2 ? l2->val : 0);
    carry = sum / 10;
    current->next = new ListNode(sum % 10);
    current = current->next;
    if (l1) l1 = l1->next;
    if (l2) l2 = l2->next;
  }
  return dummy->next;
}

This code adds two numbers represented by linked lists digit by digit, handling carry, and returns the sum as a new linked list.

Execution Table

Step	Operation	l1 Node	l2 Node	Sum	Carry	New Node Created	Result List Visual
1	Add 2 + 5 + carry 0	2	5	7	0	7	7 -> null
2	Add 4 + 6 + carry 0	4	6	10	1	0	7 -> 0 -> null
3	Add 3 + 4 + carry 1	3	4	8	0	8	7 -> 0 -> 8 -> null
4	No more nodes in l1, add 0 + 9 + carry 0	null	9	9	0	9	7 -> 0 -> 8 -> 9 -> null
5	No more nodes in l1 and l2, carry 0, stop	null	null	0	0	none	7 -> 0 -> 8 -> 9 -> null

💡 Both lists are fully traversed and carry is zero, so addition stops.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
carry	0	0	1	0	0	0
l1	2 -> 4 -> 3 -> null	4 -> 3 -> null	3 -> null	null	null	null
l2	5 -> 6 -> 4 -> 9 -> null	6 -> 4 -> 9 -> null	4 -> 9 -> null	9 -> null	null	null
result list	empty	7 -> null	7 -> 0 -> null	7 -> 0 -> 8 -> null	7 -> 0 -> 8 -> 9 -> null	7 -> 0 -> 8 -> 9 -> null

Key Moments - 3 Insights

Why do we continue adding even when one list is shorter and becomes null?

As shown in step 4 of execution_table, when l1 is null but l2 still has nodes, we treat l1's value as 0 and continue adding to include all digits.

How is the carry handled when sum is 10 or more?

In step 2, sum is 10, so carry becomes 1 for the next addition, and the current node stores sum % 10 which is 0, as shown in the execution_table.

Why do we create a dummy node at the start?

The dummy node simplifies adding new nodes and returning the result list head, avoiding special cases for the first node, as seen in the code sample.

Visual Quiz - 3 Questions

Look at the execution_table, what is the carry value after step 2?

A 1

B 0

C 2

D None

💡 Hint

Check the 'Carry' column in row for step 2 in execution_table.

At which step does the result list first contain the node with value 8?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the 'Result List Visual' column in execution_table to see when 8 appears.

If the carry was not handled, what would happen to the result list after step 2?

A It would be the same as current

B It would miss the carry digit, resulting in wrong sum

C It would add extra nodes unnecessarily

D It would cause an infinite loop

💡 Hint

Refer to the 'Carry' and 'New Node Created' columns in execution_table for step 2.

Concept Snapshot

Add digits from two linked lists node by node.
Keep track of carry from sum > 9.
Create new nodes for each sum digit.
Continue until both lists and carry are empty.
Use a dummy node to simplify list construction.

Full Transcript

This concept adds two numbers represented as linked lists. We start from the head nodes of both lists, add their values along with any carry from previous addition. The sum's last digit is stored in a new node in the result list, and the carry is passed to the next addition. We move pointers forward in both lists. If one list ends earlier, we treat its value as zero and continue. We stop when both lists are fully traversed and no carry remains. A dummy node helps build the result list easily. The execution table shows each step's sum, carry, and the growing result list. Key moments clarify why carry is important, why we continue when one list ends, and why a dummy node is used.

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