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.