Add Two Numbers Represented as Linked List in DSA Python

Mental Model

Each linked list holds a number in reverse order, and we add digits one by one like elementary addition with carry.

Analogy: Imagine adding two numbers digit by digit from right to left, just like adding two numbers on paper starting from the units place.

List1: 2 -> 4 -> 3 -> null
List2: 5 -> 6 -> 4 -> null
Each node holds one digit, starting from the smallest place value.

Dry Run Walkthrough

Input: list1: 2->4->3 (represents 342), list2: 5->6->4 (represents 465)

Goal: Add the two numbers and return the sum as a linked list in the same reversed digit format.

Step 1: Add first digits 2 + 5 = 7, no carry

Result: 7 -> null

Why: Start adding from the units place, store sum digit in new list

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

Result: 7 -> 0 -> null

Why: Sum exceeds 9, so keep 0 and carry 1 to next digit

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

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

Why: Add last digits plus carry, store result digit

Result:

7 -> 0 -> 8 -> null (represents 807)

Annotated Code

DSA Python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:
    dummy_head = ListNode(0)
    current = dummy_head
    carry = 0
    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
        if l1:
            l1 = l1.next
        if l2:
            l2 = l2.next
    return dummy_head.next

def printList(node: ListNode):
    while node:
        print(node.val, end='')
        if node.next:
            print(' -> ', end='')
        node = node.next
    print(' -> null')

# Driver code
# Create list1: 2 -> 4 -> 3 -> null
l1 = ListNode(2, ListNode(4, ListNode(3)))
# Create list2: 5 -> 6 -> 4 -> null
l2 = ListNode(5, ListNode(6, ListNode(4)))
result = addTwoNumbers(l1, l2)
printList(result)

while l1 or l2 or carry:

continue adding while there are digits or carry left

val1 = l1.val if l1 else 0 val2 = l2.val if l2 else 0

get current digit values or 0 if list ended

total = val1 + val2 + carry carry = total // 10

sum digits and update carry for next addition

current.next = ListNode(total % 10) current = current.next

create new node with sum digit and move pointer

if l1: l1 = l1.next if l2: l2 = l2.next

advance input list pointers to next digits

Output

7 -> 0 -> 8 -> null

Complexity Analysis

Time: O(max(m, n)) because we traverse both lists once where m and n are their lengths

Space: O(max(m, n)) for the output list which can be at most one digit longer than inputs

vs Alternative: This approach is efficient compared to converting lists to numbers and back, which can cause overflow and extra conversions

Edge Cases

One list is empty

The function returns the other list as the sum

DSA Python

val1 = l1.val if l1 else 0

Sum results in an extra digit carry (e.g., 5 + 5 = 10)

An extra node is added to hold the carry digit

DSA Python

while l1 or l2 or carry:

Lists of different lengths

Shorter list digits are treated as 0 after end

DSA Python

val2 = l2.val if l2 else 0

When to Use This Pattern

When you see two numbers stored as linked lists with digits in reverse order, use digit-by-digit addition with carry to sum them efficiently.

Common Mistakes

Mistake: Not handling the carry after the last digits are added
Fix: Include carry in the while loop condition to add an extra node if needed

Mistake: Advancing pointers without checking if they are None
Fix: Check if l1 or l2 is not None before moving to next node

Summary

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

Use when numbers are too large to convert to integers or are given as linked lists.

Add digits from right to left, keep track of carry, and build the result list on the go.