2. Add Two Numbers
## description
## 2. Add Two Numbers
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. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example 1:
1Input: l1 = [2,4,3], l2 = [5,6,4]
2Output: [7,0,8]
3Explanation: 342 + 465 = 807.Example 2:
1Input: l1 = [0], l2 = [0]
2Output: [0]Example 3:
1Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
2Output: [8,9,9,9,0,0,0,1]- –The number of nodes in each linked list is in the range [1, 100].
- –0 <= Node.val <= 9
- –It is guaranteed that the list represents a number that does not have leading zeros.
Constraints:
## notes
### Intuition
Since the digits are stored in reverse order, we can add them just like we would on paper—starting from the ones place and carrying over when the sum exceeds 9.
### Implementation
Create a dummy node for the result and maintain pointers for both input lists and the result. Track a carry value initialized to 0. While both lists have nodes, compute p1.val + p2.val + carry. The new digit is total % 10 and the new carry is total // 10. Create a new node and advance all pointers. After the main loop, process any remaining nodes in either list with the same carry logic.
### Edge-cases
After processing both lists, the carry might still be non-zero (e.g., 99 + 1 = 100). Create a final node with the carry value if needed.
- –Time: O(n) — traverse both lists once
- –Space: O(1) — result list doesn't count toward space complexity
### Complexity
## solution
1from typing import Optional
2from lcutils import ListNode
3
4# Definition for singly-linked list.
5# class ListNode:
6# def __init__(self, val=0, next=None):
7# self.val = val
8# self.next = next
9class Solution:
10 def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
11 dummy = ListNode()
12 p1, p2, curr = l1, l2, dummy
13 carry = 0
14
15 while p1 and p2:
16 tot = p1.val + p2.val + carry
17 val = tot
18 carry = 0
19
20 if tot >= 10:
21 val = tot % 10
22 carry = tot // 10
23
24 curr.next = ListNode(val)
25 curr = curr.next
26 p1 = p1.next
27 p2 = p2.next
28
29 while p1:
30 tot = p1.val + carry
31 val = tot
32 carry = 0
33
34 if tot >= 10:
35 val = tot % 10
36 carry = tot // 10
37
38 curr.next = ListNode(val)
39 curr = curr.next
40 p1 = p1.next
41
42 while p2:
43 tot = p2.val + carry
44 val = tot
45 carry = 0
46 if tot >= 10:
47 val = tot % 10
48 carry = tot // 10
49
50 curr.next = ListNode(val)
51 curr = curr.next
52 p2 = p2.next
53
54 if carry:
55 curr.next = ListNode(carry)
56
57 return dummy.next
58
59
60
61
62if __name__ == "__main__":
63 # Include one-off tests here or debugging logic that can be run by running this file
64 # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
65 solution = Solution()
66