[LeetCode] Add Two Numbers

Problem: 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:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Input: l1 = [0], l2 = [0]
Output: [0]

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

Approach: It's an implementation problem, just look at the implementation to understand the approach.

Implementation in C#:

    public ListNode AddTwoNumbers(ListNode l1, ListNode l2)

    {

        if (l1 == null || l2 == null)

        {

            if (l1 == null)

            {

                return l2;

            }

            return l1;

        }

        ListNode sumHead = new ListNode();

        ListNode itr = sumHead;

        int carry = 0;

        while (l1 != null && l2 != null)

        {

            int sum = l1.val + l2.val + carry;

            carry = sum / 10;

            sum = sum % 10;

            itr.next = new ListNode(sum);

            l1 = l1.next;

            l2 = l2.next;

            itr = itr.next;

        }

        if (l1 != null)

        {

            this.CarrySum(l1, ref itr, ref carry);

        }

        else if(l2 != null)

        {

            this.CarrySum(l2, ref itr, ref carry);

        }

        if (carry != 0)

        {

            itr.next = new ListNode(carry);

        }

        return sumHead.next;

    }

    private void CarrySum(ListNode l, ref ListNode itr, ref int carry)

    {

        while (l != null && carry != 0)

        {

            int sum = l.val + carry;

            carry = sum / 10;

            sum = sum % 10;

            itr.next = new ListNode(sum);

            l = l.next;

            itr = itr.next;

        }

        if (l != null)

        {

            itr.next = l;

        }

    }

Complexity: O(n)