Add two numbers
A non-negative whole number can be stored as a linked list with one digit per node, ones digit first: 352 is stored as 2 → 5 → 3. Each node is a ListNode with a value (node.val, one digit) and a link (node.next) to the node after it.
You get l1 and l2, the first nodes of two such lists. Return the first node of a list that stores their sum the same way: one digit per node, ones digit first.
No number has leading zeros, so no list ends in a 0 node. The one exception is zero, stored as a single node holding 0. Your answer must follow the same rule.
Examples write a linked list as the list of its values: [2, 5, 3] means 2 → 5 → 3, the number 352.
l1 = [2, 5, 3], l2 = [4, 7]Output[6, 2, 4]352 + 74 = 426, stored ones digit first.
l1 = [9, 9], l2 = [1]Output[0, 0, 1]99 + 1 = 100. The last carry needs a third node.
l1 = [0], l2 = [0]Output[0]0 + 0 = 0, a single node.
1 ≤ number of nodes in each list ≤ 105
0 ≤ node value ≤ 9
No list ends in a 0 node unless it is the single node 0.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.