Add Two Numbers II — LeetCode 445 Python Solution
MediumStackLinked ListMath
- Problem
- #445
- Pattern
- Linked List
- Reading time
- 4 min
- Source
- leetcode.com
The problem
You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contains a single digit.
Example
- Input
- l1 = [7,2,4,3], l2 = [5,6,4]
- Output
- [7,8,0,7]
Python solution
Python
# 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]:
s1, s2 = [], []
while l1:
s1.append(l1.val)
l1 = l1.next
while l2:
s2.append(l2.val)
l2 = l2.next
dummy = ListNode()
carry = 0
while s1 or s2 or carry:
s = (0 if not s1 else s1.pop()) + (0 if not s2 else s2.pop()) + carry
carry, val = divmod(s, 10)
# node = ListNode(val, dummy.next)
# dummy.next = node
dummy.next = ListNode(val, dummy.next)
return dummy.nextComplexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
Pattern: Linked List
Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 445. Add Two Numbers II 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
Frequently asked questions
- How hard is LeetCode 445. Add Two Numbers II?
- LeetCode 445. Add Two Numbers II is rated Medium on LeetCode.
- What is the time complexity of LeetCode 445. Add Two Numbers II?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 445. Add Two Numbers II?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 445. Add Two Numbers II cover?
- LeetCode 445. Add Two Numbers II is tagged Stack, Linked List and Math on LeetCode.