Problem
Given two non-empty linked lists representing two non-negative integers, add the two numbers and return the result as a linked list.The digits are stored in reverse order, and each node contains a single digit. The two numbers may have different lengths.
Example(s)
Consider the following examples to understand the expected input and output.Example 1
Input
l1 = [2,4,3]
l2 = [5,6,4]Output
[7,0,8]Example 2
Input
l1 = [9,9,9,9,9,9,9]
l2 = [9,9,9,9]Output
[8,9,9,9,0,0,0,1]Solution
This solution uses the Linked List pattern. We traverse both linked lists from left to right, adding the corresponding digits along with any carry from the previous addition.Since the digits are already stored in reverse order, the least significant digits are processed first. We create a new node for each resulting digit and continue until both lists and the carry are completely processed.
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode result = new ListNode(0);
ListNode current = result;
int carry = 0;
// Keep looping if there are remaining digits in l1 OR l2, or if a carry is left over
while (l1 != null || l2 != null || carry != 0) {
int sum = carry;
if (l1 != null) {
sum += l1.val;
l1 = l1.next;
}
if (l2 != null) {
sum += l2.val;
l2 = l2.next;
}
carry = sum / 10; // Extracts the carry (e.g., 12 / 10 = 1)
current.next = new ListNode(sum % 10); // Extracts the single digit (e.g., 12 % 10 = 2)
current = current.next;
}
return result.next;
}
}Complexity
We traverse each linked list once, so the time complexity isO(max(m, n)), where m and n are the lengths of the two linked lists.
The result contains at most
max(m, n) + 1 nodes, so the space complexity is O(max(m, n)) for the output list.
