2. Add Two Numbers - LeetcodeSolve

Explanation

To solve this problem, we iterate through both linked lists simultaneously, adding the corresponding digits along with any carry from the previous step. We create a dummy node to hold the result and maintain a current pointer to track the current node we are working on. We keep iterating until both input linked lists are processed and there is no carry left. At each step, we update the carry, create a new node for the result, and move the current pointer to the next node.

Algorithm:

Initialize a dummy node and a current node to track the result linked list.
Initialize carry as 0.
Iterate through both input linked lists until we reach the end of both lists and there is no carry left.
At each step, calculate the sum of two digits along with the carry.
Update the carry for the next iteration.
Create a new node with the sum % 10 and move the current pointer.
Finally, return the next node of the dummy node as the head of the result linked list.

Time Complexity: O(max(N, M)), where N and M are the lengths of the two input linked lists.

Space Complexity: O(max(N, M)), for the result linked list.

View Leetcode Problem

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        int carry = 0;
        
        while (l1 != null || l2 != null || carry > 0) {
            int sum = carry;
            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }
            
            carry = sum / 10;
            current.next = new ListNode(sum % 10);
            current = current.next;
        }
        
        return dummy.next;
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

Add import statement if required.
Optimize the code for better time or space complexity.
Add test cases to validate edge cases and common scenarios.
Handle error conditions or invalid inputs gracefully.
Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.