MediumNo. 0002

Add Two Numbers — LeetCode 2 Python Solution

Topics
Recursion, Linked List, Math
Reading time
3 min

The problem

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit.

Example

Input
l1 = [2,4,3], l2 = [5,6,4]
Output
[7,0,8]
Explanation
342 + 465 = 807.

Python solution

PythonSolution
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(
        self, l1: Optional[ListNode], l2: Optional[ListNode]
    ) -> Optional[ListNode]:
        dummy = ListNode()
        carry, curr = 0, dummy
        while l1 or l2 or carry:
            s = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry
            carry, val = divmod(s, 10)
            curr.next = ListNode(val)
            curr = curr.next
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None
        return dummy.next

Complexity

Time
O(max (m, n))where m and n are the lengths of the two linked lists
Space · auxiliary
O(1)

Pattern: Linked List

Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 2. Add Two Numbers is filed here because LeetCode tags it Linked List, which is the vocabulary this hub collects.

The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.

Related problems

Related problems
No.ProblemDifficulty
0445Add Two Numbers IIMedium
0050Pow(x, n)Medium
0060Permutation SequenceHard
0273Integer to English WordsHard
0326Power of ThreeEasy
0382Linked List Random NodeMedium

Frequently asked questions

How hard is LeetCode 2. Add Two Numbers?

LeetCode 2. Add Two Numbers is rated Medium on LeetCode.

What is the time complexity of LeetCode 2. Add Two Numbers?

The Python solution on this page runs in O(max (m, n)), where m and n are the lengths of the two linked lists.

What is the space complexity of LeetCode 2. Add Two Numbers?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 2. Add Two Numbers cover?

LeetCode 2. Add Two Numbers is tagged Recursion, Linked List and Math on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.