Understand what the interviewer is asking for by using test cases and questions about the problem.
- Established a set (2-3) of test cases to verify their own solution later.
- Established a set (1-2) of edge cases to verify their solution handles complexities.
- Have fully understood the problem and have no clarifying questions.
- Have you verified any Time/Space Constraints for this problem?
HAPPY CASE
Input: 2->4->3, 5->6->4
Output: 7->0->8
Input: 0, 0
Output: 0
EDGE CASE
Input: 9->9->9->9->9->9->9, 9->9->9->9
Output: 8->9->9->9->0->0->0->1
Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.
For Linked Lists problems, we want to consider the following approaches:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Iterate through both lists and sum the values of the nodes and remainder from the previous addition for each new node.
1) Create a dummy head. This will be our reference to our return list.
2) Create a curr pointer that helps us build the return list
3) Initialize a variable to store the remainder value, if any, as we compute the sum.
4) Traverse the two lists while our two pointers is not null and remainder is not 0.
a) Find the values at each pointer
b) Find and store their sum
c) Calculate the carry over value, if any
d) Create and attach a new node with summed value to the return list.
e) Repeat with next nodes
5) Return dummy.next
⚠️ Common Mistakes
Implement the code to solve the algorithm.
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
# Create a dummy head. This will be our reference to our return list + Create a curr pointer that helps us build the return list
dummyNode = curr = ListNode()
# Initialize a variable to store the remainder value, if any, as we compute the sum.
remainder = 0
# Traverse the two lists while our two pointers is not null and remainder is not 0.
while l1 or l2 or remainder:
# Find the values at each pointer
num1 = l1.val if l1 else 0
num2 = l2.val if l2 else 0
# Find and store their sum
total = num1 + num2 + remainder
singleDigitTotal = total % 10
# Calculate the carry over value, if any
remainder = total // 10
# Create and attach a new node with summed value to the return list
curr.next = ListNode(singleDigitTotal)
# Repeat with next nodes
curr = curr.next
if l1:
l1 = l1.next
if l2:
l2 = l2.next
# Return dummy.next
return dummyNode.next
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// Create a dummy head. This will be our reference to our return list.
ListNode dummyHead = new ListNode(0);
// Create a curr pointer that helps us build the return list
ListNode curr = dummyHead;
// Initialize a variable to store the remainder value, if any, as we compute the sum
int remainder = 0;
// Traverse the two lists while our two pointers is not null and remainder is not 0
while (l1 != null || l2 != null || remainder != 0) {
// Find the values at each pointer
int x = (l1 != null) ? l1.val : 0;
int y = (l2 != null) ? l2.val : 0;
// Find and store their sum
int sum = remainder + x + y;
// Calculate the carry over value, if any
remainder = sum / 10;
// Create and attach a new node with summed value to the return list.
curr.next = new ListNode(sum % 10);
// Repeat with next nodes
curr = curr.next;
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}
// Return dummy.next
return dummyHead.next;
}
}
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Assume N
represents the number of nodes in the linked list 1. M
represents the number of nodes in the linked list 2.
O(N + M)
because we need to traverse all numbers in both linked listO(N or M)
because the maximum number of digit we need to store is the number of digits in the longer list plus one more digit. I.E. 999 + 999 = 8991 or 1 + 99 = 001