Add Two Numbers

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]

Constraints:

• The number of nodes in each linked list is in the range [1, 100].

• 0 <= Node.val <= 9

• It is guaranteed that the list represents a number that does not have leading zeros.

Hint

Approach : Elementary Math

Intuition

Keep track of the carry using a variable and simulate digits-by-digits sum starting from the head of list, which contains the least-significant digit.

Figure 1. Visualization of the addition of two numbers: 342+465=807342 + 465 = 807342+465=807.
Each node contains a single digit and the digits are stored in reverse order.

Algorithm

Just like how you would sum two numbers on a piece of paper, we begin by summing the least-significant digits, which is the head of l1l1l1 and l2l2l2. Since each digit is in the range of 0…90 \ldots 90…9, summing two digits may "overflow". For example 5+7=125 + 7 = 125+7=12. In this case, we set the current digit to 222 and bring over the carry=1carry = 1carry\=1 to the next iteration. carrycarrycarry must be either 000 or 111 because the largest possible sum of two digits (including the carry) is 9+9+1=199 + 9 + 1 = 199+9+1=19.

The pseudocode is as following:

• Initialize current node to dummy head of the returning list.

• Initialize carry to 000.

• Loop through lists l1l1l1 and l2l2l2 until you reach both ends and carry is 000.

  • Set xxx to node l1l1l1's value. If l1l1l1 has reached the end of l1l1l1, set to 000.

  • Set yyy to node l2l2l2's value. If l2l2l2 has reached the end of l2l2l2, set to 000.

  • Set sum=x+y+carrysum = x + y + carrysum\=x+y+carry.

  • Update carry=sum/10carry = sum / 10carry\=sum/10.

  • Create a new node with the digit value of (sum mod 10)(sum \bmod 10)(summod10) and set it to current node's next, then advance current node to next.

  • Advance both l1l1l1 and l2l2l2.

• Return dummy head's next node.

Note that we use a dummy head to simplify the code. Without a dummy head, you would have to write extra conditional statements to initialize the head's value.

Take extra caution of the following cases:

l2=[0,1,2]l2=[0,1,2]l2=[0,1,2] | When one list is longer than the other. | | l1=[]l1=[]l1=[]
l2=[0,1]l2=[0,1]l2=[0,1] | When one list is null, which means an empty list. | | l1=[9,9]l1=[9,9]l1=[9,9]
l2=[1]l2=[1]l2=[1] | The sum could have an extra carry of one at the end, which is easy to forget. |

But the solution I had submitted did not use this approach.

Solution

using System.Numerics;

public class Solution {
    public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
        BigInteger intA = GetWholeNumber(l1);
        BigInteger intB = GetWholeNumber(l2);
        BigInteger intC = intA + intB;
        ListNode l3 = ConvertToListNode(intC);
        return l3;
    }

    //Get the whole reversed number from the list node
    public BigInteger GetWholeNumber(ListNode currentNode)
    {
        if (currentNode == null) {
            return 0;  // Handle empty list case
        }

        string strNumber = "";
        while (currentNode != null) {
            strNumber += currentNode.val.ToString();  // Correct concatenation
            currentNode = currentNode.next;
        }

        string reversedStr = string.Concat(strNumber.Reverse());  // Efficient reversal
        return BigInteger.Parse(reversedStr);
    }

    //Convert the number into listnode
    public ListNode ConvertToListNode(BigInteger number) {
    string numString = number.ToString();  // Convert to string
    string reversedString = string.Concat(numString.Reverse());

    ListNode head = null;
    ListNode currentNode = null;

    foreach (char digitChar in reversedString) {
        int digitValue = int.Parse(digitChar.ToString());
        ListNode newNode = new ListNode(digitValue);

        if (head == null) {
            head = newNode;
            currentNode = head;
        } else {
            currentNode.next = newNode;
            currentNode = newNode;
        }
    }

    return head;  // Return the head of the linked list
    }
}

Explanation

The two lists were converted to numbers and reversed using the function, "GetWholeNumber".

Then the two numbers are added and the new number is reversed and then converted to a List using the function, "ConvertToListNode".

The code is pretty much straight forward. Though it is not the best and elegant solution, the result was pretty much impressive.