Problem
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:
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:
Input: l1 = [0], l2 = [0]
Output: [0]
Example 3:
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [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.
Solution
/**
* 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; }
* }
*/
import java.util.Objects;
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int carry = 0;
ListNode head = null;
ListNode intermediate = null;
while(l1 != null || l2 != null) {
int sum = carry;
if(l1 != null){
sum += l1.val;
l1 = l1.next;
}
if(l2 != null){
sum += l2.val;
l2 = l2.next;
}
carry = sum /10;
ListNode node = new ListNode(sum % 10);
if (Objects.isNull(head)) {
head = intermediate = node;
} else {
intermediate.next = node;
intermediate = intermediate.next;
}
}
if (carry > 0) {
intermediate.next = new ListNode(carry);
}
return head;
}
}
The above solution is for adding two numbers that are represented as linked lists, where each node in the linked list contains a single digit of the number. The solution uses a straightforward approach to iterate through both linked lists and perform the addition, considering the carry value. Here's how the code works:
- The
addTwoNumbers
function takes two linked list inputsl1
andl2
, which represent the two numbers to be added. - It initializes variables
carry
,head
, andintermediate
. - The loop iterates while either
l1
orl2
has more digits or there's a carry value. - Inside the loop:
- It calculates the sum of the digits along with the carry value.
- Creates a new node with the least significant digit of the sum and potentially the carry from the previous step.
- Updates the
intermediate
node'snext
pointer to the newly created node. - Moves to the next digit in both
l1
andl2
if they exist. - Updates the
carry
for the next iteration.
- After the loop, if there's still a carry left, it creates an additional node to represent it.
- The
head
node is returned, which points to the beginning of the resulting linked list.
This code effectively performs the addition of two numbers represented as linked lists while considering carry values. It constructs the resulting linked list digit by digit and handles the carry properly.
Please note that you need to make sure the ListNode
class is defined properly and imported.
Related Articles
- LeetCode 01 : Two Sum
- LeetCode 02 : Add Two Numbers
- LeetCode 03 : Longest Substring Without Repeating Characters
- LeetCode 04 : Container With Most Water
- LeetCode 05 : Remove Duplicates from Sorted Array
- LeetCode 06 : Maximum Subarray
- LeetCode 07 : Contains Duplicate
- Codechef 01 : Problem Code: AGELIMIT
- Codechef 02 : Problem Code: BURGERS