Add Two Numbers (LeetCode)
Published:
2. 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.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example 1:
[Diagram: 2->4->3, 5->6->4, and 7->0->8]
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.
Example 2:
Input: l1 = [0], l2 = [0]
Output: [0]
This question includes visual content: The image shows three horizontal chains of circles (linked lists). The first chain has circles containing numbers 2, 4, 3 with arrows pointing right. The second chain has circles containing numbers 5, 6, 4 with arrows pointing right. A horizontal line separates these from the third chain, which has circles containing numbers 7, 0, 8 with arrows pointing right. These illustrate that (2 -> 4 -> 3) + (5 -> 6 -> 4) = (7 -> 0 -> 8).
Animated Video Solution
The first half plays free, the full solution is in the app.
Step by Step Written Solution
Hi Mustafa, let's solve this linked list problem together. We need to add two numbers stored as linked lists where the digits are in reverse order.
Add Two Numbers
Notice that since the digits are in reverse order, the head of each list represents the ones place. This is perfect, because we can iterate through both lists simultaneously and perform addition just like we do with pen and paper.
Strategy
1. Initialize a dummy head node for the result list.
2. Keep a variable for the carry, starting at zero.
3. Iterate until both input lists are exhausted and the carry is zero.
In each step, we calculate the sum of the current digits from both lists plus the carry. The digit for our result node is the sum modulo ten, and the new carry is the sum divided by ten.
The Logic
Let's look at the example: two four three plus five six four. Starting at the heads, two plus five is seven, no carry.
Step 1: 2 + 5 = 7
Moving to the next nodes, four plus six is ten. We keep the zero and our carry becomes one.
Step 2: 4 + 6 = 10
The rest of this solution is on Solvi
4 more steps are locked. Watch the full animated, narrated solution for free.
Snap a photo, solve any question like this.
Watch the Rest for Free
Free to download · First solutions are on us
