Add Two Numbers
Two linked lists represent nonnegative integers with the least significant digit first. Add the integers and return the result in the same form.
Work through the cases
3 examplesInput notation
Two lines of digits separated by spaces; each list is nonempty.Expected result
The sum as digits, least significant first.Case 1
Input
3 4 2 7 6
Expected output
0 1 3
Case 2
Input
9 9 1
Expected output
0 0 1
Case 3
Input
0 0
Expected output
0
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
The first idea is to convert both lists to integers and add. Length is at most 100, so big integers would pass, but the lists already store digits in reverse—this is column addition. Converting away from the list throws that structure away. The issue is not arithmetic volume: the lists may differ in length, and a final carry may remain. Each position is “the two digits (missing treated as 0) plus carry”, then split into a new digit and a new carry. So we grow the answer from a dummy node and walk both lists together. The loop must continue while l_1, l_2, or carry remains; otherwise [9]+[1] drops the leading 1.
We traverse two linked lists l_1 and l_2 at the same time, and use the variable carry to indicate whether there is a carry.
Each time we traverse, we take out the current bit of the corresponding linked list, calculate the sum with the carry carry, and then update the value of the carry. Then we add the current bit to the answer linked list. If both linked lists are traversed, and the carry is 0, the traversal ends.
Finally, we return the head node of the answer linked list.
The time complexity is O(\max (m, n)), where m and n are the lengths of the two linked lists. We need to traverse the entire position of the two linked lists, and each position only needs O(1) time. Ignoring the space consumption of the answer, the space complexity is O(1).
/**
* 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(0);
int carry = 0;
ListNode cur = dummy;
while (l1 != null || l2 != null || carry != 0) {
int s = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + carry;
carry = s / 10;
cur.next = new ListNode(s % 10);
cur = cur.next;
l1 = l1 == null ? null : l1.next;
l2 = l2 == null ? null : l2.next;
}
return dummy.next;
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.