Coding Challenge from Leetcode - Add Two Numbers!
Here is the problem and solution to a coding challenge from Leetcode.com called Add Two Numbers!
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. 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.
Intuition / Tip
Iterate through both linked lists simultaneously, adding corresponding digits. Handle carry-over whenever the sum exceeds 9, and make sure to process any remaining carry after reaching the end of both lists.
Solution Steps
- Initialize pointers for both linked lists and a dummy node for the result.
- Set up a carry variable to store sums greater than 9.
- Iterate through the lists, adding corresponding digits along with the carry.
- Create new nodes in the result list to store the sum of the digits.
- Handle cases where one list is longer than the other.
- Add a final node if there is a remaining carry after both lists are processed.
/** | |
* Definition for singly-linked list. | |
* function ListNode(val, next) { | |
* this.val = (val===undefined ? 0 : val) | |
* this.next = (next===undefined ? null : next) | |
* } | |
* | |
* @param {ListNode} l1 | |
* @param {ListNode} l2 | |
* @return {ListNode} | |
*/ | |
const addTwoNumbers = function(l1, l2) { | |
const l3 = new ListNode(null, null); | |
let l1Pointer = l1; | |
let l2Pointer = l2; | |
let l3Pointer = l3; | |
let remainder = 0; | |
while (l1Pointer || l2Pointer || remainder) { | |
const sum = remainder + | |
(l1Pointer?.val ?? 0) + (l2Pointer?.val ?? 0); | |
l3Pointer.val = sum % 10; | |
remainder = (sum > 9) ? 1 : 0; | |
l1Pointer = l1Pointer?.next; | |
l2Pointer = l2Pointer?.next; | |
if (l1Pointer || l2Pointer || remainder) { | |
l3Pointer.next = new ListNode(null, null); | |
l3Pointer = l3Pointer.next; | |
} | |
} | |
return l3; | |
}; |
Time Complexity
O(max(n, m)), where n and m are the lengths of the two linked lists, as we iterate through both lists.
Space Complexity
O(max(n, m)), since we create a new linked list to store the result, with space proportional to the larger of the two inputs.
External Resources
- View the original challenge on Leetcode
- Learn more about linked lists: Wikipedia: Linked Lists
- Brush up on GeeksforGeeks: Data Structures - Linked Lists
Let me know if you have any questions or see ways I could have optimized!