LeetCode 2. Add Two Numbers | LinkedList

 class Solution {

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        ListNode head = new ListNode(0);

        ListNode curr = head;

        int carry = 0;

        while(l1 != null || l2 != null || carry > 0) {

            int val1 = l1 != null ? l1.val : 0;

            int val2 = l2 != null ? l2.val : 0;

            int sum = val1 + val2 + carry;

            carry = sum / 10;

            curr.next = new ListNode(sum % 10);

            curr = curr.next;

            l1 = l1 != null ? l1.next : null;

            l2 = l2 != null ? l2.next : null;

        }

        //if(carry > 0)

        //    curr.next = new ListNode(carry);

        return head.next;

    }

}

Time Complexity: O(n)
Space Complexity: O(n) or O(1)

n is the number of nodes in the longer list.

One might argue that we are using another linked list `head` to store our result so the space complexity should be O(n). But this is the list we are not using for our algorithm, we are using it for the result which is asked in the question.