700043. Add Number Linked Lists
Add Number Linked Lists
Summary
Given two non-empty linked lists representing numbers in their respective linked list form, add them together and return a new linked list. The linked lists may contain digits 0-9, and the result should also be represented as a linked list.
For example, if we have two linked lists 1 -> 2 -> 3 (which represents the number 123) and 4 -> 5, adding them together would result in the linked list 5 -> 7 -> 3 (which represents the number 507).
Detailed Explanation
To solve this problem, we can convert each linked list into an integer, add the two integers, and then construct a new linked list representing the sum.
Here's a step-by-step breakdown of the solution:
- Initialize three variables:
carry, which will store any carry-over value from adding two digits;sum, which will store the sum of the current two digits; andnewList, which will store the resulting linked list. - Traverse both linked lists simultaneously, adding corresponding digits together with the
carryvalue. - If the sum is greater than or equal to 10, update the
carryvalue and set the current digit in the result linked list to the remainder of the sum divided by 10 (i.e., the ones place). - Repeat steps 2-3 until one of the linked lists becomes empty.
- If there's a remaining
carryvalue, add it to the front of the resulting linked list.
Time complexity: O(max(m, n)), where m and n are the lengths of the input linked lists.
Space complexity: O(max(m, n)), as we need to store the resulting linked list.
Optimized Solutions
Java
class Node {
int val;
Node next;
}
public class Solution {
public Node addTwoNumbers(Node l1, Node l2) {
Node result = new Node(0);
Node current = result;
int carry = 0;
while (l1 != null || l2 != null || carry > 0) {
int sum = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + carry;
carry = sum / 10;
current.next = new Node(sum % 10);
current = current.next;
l1 = l1 != null ? l1.next : null;
l2 = l2 != null ? l2.next : null;
}
return result.next;
}
}