Description
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:
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.
Example 2:
Input: l1 = [0], l2 = [0]
Output: [0]
Example 3:
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]
Constraints:
- 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.
Approach
- Iterate the list with condition discussed below and add elements and carry then update carry and the added number so as to only have ones place
- Condition used here is such we keep adding till the bigger one gets exhausted and assume zero if the shorter one is zero and the condition is added for carry so as to make sure even after the lists are Iterated there could still be some leftover carry
Time:O(n) Space: O(n)- It says m + n check once- It’s is easier because it is already in reverse I guess with non reverse we create method to reverse and reverse the lists then find answer in list then reverse it to get the right answer
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode();
ListNode sum = dummy;
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
int v1 = l1 != null ? l1.val : 0;
int v2 = l2 != null ? l2.val : 0;
int v = v1 + v2 + carry;
carry = v / 10;
v = v % 10;
sum.next = new ListNode(v);
sum = sum.next;
if (l1 != null)
l1 = l1.next;
if (l2 != null)
l2 = l2.next;
}
return dummy.next;
}
}