1. Introduction
In this blog post, we explore the "Add Two Numbers" problem, a common algorithmic programming challenge involving adding two numbers represented as linked lists. We will solve this problem using Java, offering a deep dive into handling data structures like singly-linked lists.
Problem
Given two non-empty linked lists representing two non-negative integers, where the digits are stored in reverse order and each node contains a single digit, your task is to add these numbers and return the sum as a linked list. Assume there are no leading zeros, except for the number 0 itself.
2. Solution Steps
1. Create a dummy head node to simplify list manipulation.
2. Iterate through both lists, adding corresponding digits and any carry from the previous sum.
3. For each sum, create new nodes, handling carry-over for sums above 9.
4. Continue this process until both lists are fully traversed.
5. If there's a remaining carry, create an additional node for it.
3. Code Program
// Node structure for linked list
public class ListNode {
int val; // Value of the node
ListNode next; // Reference to the next node
// Constructor to initialize the node with a value
ListNode(int x) { val = x; }
// Method to print the linked list starting from this node
void printList() {
ListNode temp = this;
while(temp != null) {
System.out.print(temp.val + " "); // Print the value of the current node
temp = temp.next; // Move to the next node
}
System.out.println();
}
}
// Solution class to add two numbers
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(0); // Dummy head to simplify list manipulation
ListNode p = l1, q = l2, curr = dummyHead; // Pointers for iterating over lists
int carry = 0; // Variable to store carry
// Iterate until both lists are fully traversed
while (p != null || q != null) {
int x = (p != null) ? p.val : 0; // Value from list l1 or 0 if null
int y = (q != null) ? q.val : 0; // Value from list l2 or 0 if null
int sum = carry + x + y; // Sum of current digits and carry
carry = sum / 10; // Update carry for the next iteration
curr.next = new ListNode(sum % 10); // Create new node with the single digit
curr = curr.next; // Move to the next node in the result list
if (p != null) p = p.next; // Move to the next node in l1
if (q != null) q = q.next; // Move to the next node in l2
}
// Handle remaining carry
if (carry > 0) {
curr.next = new ListNode(carry); // Create a node with the remaining carry
}
return dummyHead.next; // Return the sum list, excluding the dummy head
}
}
// Example usage and testing
public class Main {
public static void main(String[] args) {
ListNode l1 = new ListNode(2); // First node of first list
l1.next = new ListNode(4); // Second node of first list
l1.next.next = new ListNode(3); // Third node of first list
ListNode l2 = new ListNode(5); // First node of second list
l2.next = new ListNode(6); // Second node of second list
l2.next.next = new ListNode(4); // Third node of second list
Solution solution = new Solution();
ListNode result = solution.addTwoNumbers(l1, l2);
result.printList(); // Print the result list
}
}
Output:
7 0 8
Explanation:
The input lists (2 -> 4 -> 3) and (5 -> 6 -> 4) represent the numbers 342 and 465, respectively. When added, they equal 807. Since the lists store numbers in reverse, the output list is (7 -> 0 -> 8), representing the sum of 807.
Comments
Post a Comment
Leave Comment