Add Two Numbers medium

Problem Statement

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.

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]

Steps

1. Initialization: Create a dummy node to simplify handling the head of the result list. Initialize a carry variable to 0.
2. Iteration: Iterate through the lists simultaneously until both are exhausted.
3. Summation: For each position, sum the digits from l1, l2, and the carry.
4. Node Creation: Create a new node with the ones digit of the sum and append it to the result list.
5. Carry Update: Update the carry to the tens digit of the sum.
6. Handle Remaining Nodes: If one list is longer than the other, continue processing the remaining nodes of the longer list.
7. Handle Final Carry: If there's a remaining carry after processing all nodes, add a new node for it.
8. Return Result: Return the head of the result list (excluding the dummy node).

Explanation

The solution simulates manual addition. We process the digits from least significant to most significant (because the lists are in reversed order). The carry variable keeps track of any overflow from the previous digit addition. The dummy node simplifies the process of building the linked list, avoiding special handling for the first node.

Code

using System;
using System.Collections.Generic;

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0); // Dummy node
        ListNode current = dummyHead;
        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; // Calculate carry
            int digit = sum % 10; // Calculate digit

            current.next = new ListNode(digit);
            current = current.next;
        }

        return dummyHead.next; //Return the head of the actual list (after dummy)
    }
}

Complexity

• Time Complexity: O(max(m, n)), where 'm' and 'n' are the lengths of the input lists. We iterate through each list once.
• Space Complexity: O(max(m, n)), The space used is proportional to the length of the resulting list. In the worst case, the resulting list can be as long as the longer of the two input lists plus one (for an extra carry).