Add Two Numbers — Simulate Carry with Dummy Head
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