2. Add Two Numbers

#linked-list

Problem

Add Two Numbers - LeetCodeLeetCode

Intuition

Time Complexity

Space Complexity

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; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // m -> l1.length, n -> l2.length
        // Time Complexity: O(max(m, n)), traversing through two linked lists
        // Space Complexity: O(max(m, n), storing the new linked list nodes


        // Initialize carry variable to store the carry value
        int carry = 0;

        // Create a dummy node as the head of the result list
        ListNode dummy = new ListNode();
        ListNode head = dummy;

        // Traverse both input lists until both are null
        while (l1 != null || l2 != null) {
            // Get the current values of l1 and l2
            int x = (l1 == null) ? 0 : l1.val;
            int y = (l2 == null) ? 0 : l2.val;

            // Calculate the sum of the current digits along with the carry
            int currentSum = x + y + carry;

            // Update the carry value
            carry = currentSum / 10;

            // Create a new node with the value of the sum modulo 10
            int nodeSum = currentSum % 10;
            ListNode node = new ListNode(nodeSum);

            // Connect the new node to the result list
            dummy.next = node;
            dummy = node;

            // Move to the next nodes in l1 and l2 if they are not null
            if (l1 != null) {
                l1 = l1.next;
            }

            if (l2 != null) {
                l2 = l2.next;
            }
        }

        // Check if there is still a carry remaining
        // and create a new node for it if necessary
        if (carry > 0) {
            dummy.next = new ListNode(carry);
        }

        // Return the head of the resulting list (excluding the dummy node)
        return head.next;
    }
}