Add Two Numbers Represented as Linked List in DSA Python - 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

↓

Repeat until both lists and carry are done

↓

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 Python

def addTwoNumbers(l1, l2):
    carry = 0
    dummy = ListNode(0)
    current = dummy
    while l1 or l2 or carry:
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0
        total = val1 + val2 + carry
        carry = total // 10
        current.next = ListNode(total % 10)
        current = current.next
        l1 = l1.next if l1 else None
        l2 = l2.next if l2 else None
    return dummy.next

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

Execution Table

Step	Operation	l1 Node	l2 Node	Sum (val1+val2+carry)	Carry	New Node Created	List State
1	Add 2 + 5 + 0	2	5	7	0	7	7 -> null
2	Add 4 + 6 + 0	4	6	10	1	0	7 -> 0 -> null
3	Add 3 + 4 + 1	3	4	8	0	8	7 -> 0 -> 8 -> null
4	l1 and l2 are None, carry 0	None	None	0	0	None	7 -> 0 -> 8 -> null

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

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
carry	0	0	1	0	0
l1	2 -> 4 -> 3	4 -> 3	3	None	None
l2	5 -> 6 -> 4	6 -> 4	4	None	None
current Node	dummy	7	0	8	8

Key Moments - 3 Insights

Why do we add carry to the sum each step?

Because the previous addition might have produced a carry (like 10 or more), which must be added to the next digit sum. See execution_table step 2 where carry is 1.

What happens when one list is shorter than the other?

We treat missing nodes as 0. For example, if l1 is None but l2 has nodes, val1 is 0. This is shown in variable_tracker where l1 becomes None but l2 still has nodes.

Why do we use a dummy head node?

It simplifies building the result list by avoiding special cases for the first node. The dummy's next points to the real head. See execution_table List State starting with '7 -> null'.

Visual Quiz - 3 Questions

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

A 1

B 0

C 2

D None

💡 Hint

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

At which step does the sum of digits first exceed 9, causing a carry?

A Step 1

B Step 2

C Step 3

D No step

💡 Hint

Look at the 'Sum' column in execution_table to find when sum is 10 or more.

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

A Less steps because l2 is shorter

B No change, same steps

C More steps with l2 Node as None and val2 = 0

D Carry would always be zero

💡 Hint

Refer to key_moments about handling different list lengths and variable_tracker showing l1 and l2 changes.

Concept Snapshot

Add Two Numbers as Linked Lists:
- Traverse both lists node by node
- Sum digits + carry
- Create new node with sum % 10
- Update carry = sum // 10
- Continue until both lists and carry are done
- Return list after dummy head

Full Transcript

We add two numbers represented as linked lists by traversing both lists at the same time. At each step, we add the digits from both lists plus any carry from the previous step. We create a new node with the digit part of the sum and update the carry for the next step. We continue until both lists are fully traversed and there is no carry left. A dummy head node helps simplify building the result list. This process handles different length lists by treating missing nodes as zero. The final linked list represents the sum of the two numbers.