2. Add Two Numbers

// LeetCode URL: https://leetcode.com/problems/add-two-numbers/

//   Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

/**
 * Time Complexity: O(max(M, N))
 *
 * Space Complexity: O(1)
 *
 * M = Length of list l1. N = Length of list l2
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }

        ListNode dummyHead = new ListNode(-1);
        ListNode curr = dummyHead;
        ListNode p = l1;
        ListNode q = l2;
        int carry = 0;

        while (p != null || q != null || carry > 0) {
            int sum = carry;
            if (p != null) {
                sum += p.val;
                p = p.next;
            }
            if (q != null) {
                sum += q.val;
                q = q.next;
            }
            curr.next = new ListNode(sum % 10);
            carry = sum / 10;
            curr = curr.next;
        }

        return dummyHead.next;
    }
}