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

Concept Flow - Add Two Numbers Represented as Linked List

Start with two linked lists

↓

Initialize carry = 0 and dummy head

↓

Traverse both lists simultaneously

↓

Add node values + carry

↓

Create new node with sum % 10

↓

Update carry = sum / 10

↓

Move to next nodes in both lists

↓

Repeat until both lists and carry are empty

↓

Return list starting after dummy head

We add digits node by node from two lists, keep track of carry, and build a new list with the sum.

Execution Sample

DSA C

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

// Add two numbers represented by linked lists
struct Node* addTwoNumbers(struct Node* l1, struct Node* l2) {
  // ... implementation ...
}

This code adds two numbers where each digit is a node in a linked list, returning the sum as a new linked list.

Execution Table

Step	Operation	Nodes in List (Result)	Pointer Changes	Visual State
1	Initialize carry=0, dummy head created	Empty	dummy->next = NULL	dummy -> NULL
2	Add l1=2 + l2=5 + carry=0	Create node with val=7	dummy->next = new node(7)	7 -> NULL
3	Move l1 to 4, l2 to 6; carry=0	7	current = node(7)	7 -> NULL
4	Add l1=4 + l2=6 + carry=0	Add node val=0, carry=1	current->next = new node(0)	7 -> 0 -> NULL
5	Move l1 to 3, l2 to 4; carry=1	7 -> 0	current = node(0)	7 -> 0 -> NULL
6	Add l1=3 + l2=4 + carry=1	Add node val=8, carry=0	current->next = new node(8)	7 -> 0 -> 8 -> NULL
7	Move l1 and l2 to NULL; carry=0	7 -> 0 -> 8	current = node(8)	7 -> 0 -> 8 -> NULL
8	Both lists empty, carry=0, stop	7 -> 0 -> 8	No pointer changes	7 -> 0 -> 8 -> NULL

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

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	Final
carry	0	0	1	0	0
l1	2->4->3	4->3	3	NULL	NULL
l2	5->6->4	6->4	4	NULL	NULL
current	dummy	node(7)	node(0)	node(8)	node(8)
result list	empty	7	7->0	7->0->8	7->0->8

Key Moments - 3 Insights

Why do we create a dummy head node instead of starting directly with the first sum node?

The dummy head simplifies adding nodes because it avoids checking if the result list is empty. See execution_table step 1 and 2 where dummy head is created before adding the first node.

Why do we continue the loop even if one list is shorter than the other?

We add zeros for missing nodes in the shorter list to continue addition. This is shown in execution_table steps 4 and 6 where nodes from both lists are added even if one list is shorter.

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

Carry is set to sum divided by 10 and added to next digit sum. In step 4, sum is 4+6+0=10, so node value is 0 and carry is 1 for next step.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the value of the new node created?

A 10

B 1

C 0

D 7

💡 Hint

Check the 'Nodes in List (Result)' and 'Operation' columns at step 4.

At which step does the carry become 1?

A Step 2

B Step 4

C Step 6

D Step 8

💡 Hint

Look at the 'carry' variable in variable_tracker after each step.

If the first list was longer, how would the execution_table change?

A More steps would be added to process remaining nodes of the longer list

B The carry would always be zero

C The dummy head would not be needed

D The result list would be empty

💡 Hint

Consider how the code continues until both lists and carry are empty, as shown in the flow.

Concept Snapshot

Add digits node by node from two linked lists
Keep carry for sums >= 10
Use dummy head to simplify list building
Traverse until both lists and carry are done
Return list after dummy head

Full Transcript

This concept adds two numbers represented as linked lists where each node is a digit. We start with a dummy head node to simplify building the result list. We traverse both input lists simultaneously, adding corresponding digits plus any carry from the previous addition. If one list is shorter, we treat missing nodes as zero. The sum digit is stored in a new node, and carry is updated for the next addition. We continue until both lists are fully traversed and carry is zero. The final result is the linked list starting after the dummy head node, representing the sum of the two numbers.

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