Add Two Numbers — Simulate Carry with Dummy Head

Sanjeev SharmaSanjeev Sharma
1 min read

Advertisement

Problem 221 · Add Two Numbers

Difficulty: Medium · Pattern: Carry Simulation

Numbers stored in reverse order. Return sum as reversed linked list.

Solutions

# Python
def addTwoNumbers(l1, l2):
    dummy = cur = ListNode(0)
    carry = 0
    while l1 or l2 or carry:
        a = l1.val if l1 else 0
        b = l2.val if l2 else 0
        total = a + b + carry
        carry, val = divmod(total, 10)
        cur.next = ListNode(val)
        cur = cur.next
        if l1: l1 = l1.next
        if l2: l2 = l2.next
    return dummy.next
// Java
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), cur = dummy;
    int carry = 0;
    while (l1 != null || l2 != null || carry != 0) {
        int a = l1 != null ? l1.val : 0;
        int b = l2 != null ? l2.val : 0;
        int sum = a + b + carry;
        carry = sum / 10;
        cur.next = new ListNode(sum % 10);
        cur = cur.next;
        if (l1 != null) l1 = l1.next;
        if (l2 != null) l2 = l2.next;
    }
    return dummy.next;
}

Complexity

  • Time: O(max(m,n))
  • Space: O(max(m,n))

Advertisement

Sanjeev Sharma

Written by

Sanjeev Sharma

Full Stack Engineer · E-mopro