Add two numbers (digits in reverse order)

Add two numbers stored as linked lists of digits, least-significant digit first, carrying into the next node like adding on paper.

The idea

Walk both lists together like adding two numbers by hand: add the two current digits plus any carry, write down the last digit, and carry the rest into the next column. Keep going as long as either list still has a digit or there is a carry left over.

Code

public static ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
    var dummy = new ListNode(0);
    ListNode tail = dummy;
    int carry = 0;
    while (l1 != null || l2 != null || carry != 0) {
        int sum = (l1?.val ?? 0) + (l2?.val ?? 0) + carry;
        carry = sum / 10;
        tail.next = new ListNode(sum % 10);
        tail = tail.next;
        l1 = l1?.next; l2 = l2?.next;
    }
    return dummy.next;
}

Tips

• A dummy head avoids a special case for the first digit of the result.
• Do not stop as soon as both lists end — a leftover carry still needs one more node, e.g. 5 + 5 = 10.

In the .NET library

l1?.val ?? 0 reads a digit as 0 once that list has run out, so the shorter list does not need padding with explicit zero nodes.