LeetCode's "Add Two Numbers" problem is a popular algorith challenge that involves adding two non-negative integers represented by linked lists. Each linked list stores digit in reverse order, with each node containing a single digit. Our goal is to add the two numbers and return the sum as a linked list.
Problem Descriptoin
Given two non-empty linked lists representing two non-negative integers, the digits are stored in reverse order, and each node contains a single digit. Add the two numbers and return the result as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Exmaple
(2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807
Approach
To solve this problem, we will use a dummy node to simplify the edge cases handling and iterate through both linked lists to compute the sum digit by digit while managing the carry-over value.
Solution
ListNode Class
Each node contains a value 'val' and a reference to the next node 'next'
This code is given.
class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}addTwoNumbers Method
Dummy Node: We use dummy node to simplify the code for edge cases, such as when the list is empty. The 'dummy'node serves as the starting point of the result list.
Current List: The 'current' node is used to build the result list. Initially, it points to the dummy node.
Carry Variable: The 'carry' variable holds any carry-over value from the sum of two digits.
public class AddTwoNumbersSolution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0); // Dummy node to hold the result list
ListNode current = dummy;
int carry = 0; // Variable to store the carry value
While Loop
This loop continues until both linked lists are fully traversed and there is no carry left.
Value Extraction: For each node in 'l1'and 'l2', we extract the value if the node is not null; otherwise, we use 0
Sum Calculation: We calculate the sum of the extracted values and the carry.
Carry Update. The carry is updated to 'total/10'
New Node Creation: We create a new node with the value 'total%10' and link it to the current node.
Advance Nodes: We move the 'l1','l2'and 'current' pointers to their respective next nodes.
Conclusion
This solution efficiently adds two numbers represented by linked lists in reverse order. By leveraging a dummy node and handling the carry-over value, the implementation is both clean and easy to understand. This approach ensures that we can handle any edge cases gracefully.
