Skip to content

2. Add Two NumbersΒΆ

Problem Link

To add the two numbers represented by linked lists, we traverse both lists simultaneously while maintaining a carry for digit overflow.

We use a dummy node and a pointer curr to build the result list incrementally. At each step, we compute the sum of the current digits from l1 and l2, along with the carried value from the previous step.

If a list is exhausted, we simply skip adding its value. We then create a new node with the digit total % 10 and update the carry as total // 10.

After processing both lists, if a carry remains, we append a final node to the result list. The result is returned starting from dummy.next, which represents the sum in reverse order.

Runtime Complexity

Time: \(O(n)\)

Space: \(O(1)\) if output isn't considered, \(O(n)\) if output is considered

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        carry = 0
        dummy = curr = ListNode()
        while l1 or l2:
            total = carry
            if l1:
                total += l1.val
                l1 = l1.next
            if l2:
                total += l2.val
                l2 = l2.next

            curr.next = ListNode(total%10)
            carry = total // 10
            curr = curr.next

        if carry:
            curr.next = ListNode(carry)
        return dummy.next

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    var carry, total int
    dummy := &ListNode{Val: -1}
    curr := dummy
    for l1 != nil || l2 != nil {
        total = carry
        if l1 != nil {
            total += l1.Val
            l1 = l1.Next
        }
        if l2 != nil {
            total += l2.Val
            l2 = l2.Next
        }
        curr.Next = &ListNode{Val: total % 10}
        carry = total / 10
        curr = curr.Next
    }
    if carry != 0 {
        curr.Next = &ListNode{Val: carry}
    }
    return dummy.Next
}