DSA problem
Add Two Numbers
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, also stored in reverse order.
Because the digits are stored in reverse order, the head of each list holds the least-significant digit. This is extremely convenient: it lets you process the lists in the same direction that you would perform addition by hand, starting from the ones place and moving toward higher places, propagating a carry as you go.
You may assume the two numbers do not contain any leading zero, except the number 0 itself. The two input lists may differ in length, so your traversal must continue while either list still has nodes remaining, and it must also handle a final leftover carry after both lists are exhausted.
The optimal approach is a single linear pass with a dummy head node. Walk both lists simultaneously, at each step summing the available digits plus the incoming carry; the new digit is sum % 10 and the carry forwarded is sum / 10. Using a dummy head removes any special-casing for the first node, and the result is built in O(max(m, n)) time.
Examples
l1 = [2,4,3], l2 = [5,6,4][7,0,8]l1 = [0], l2 = [0][0]l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9][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.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.